Edge-Coloring Of Hypergraphs

Hypergraphs are an important generalization of ordinary graphs. The colorings for hypergraphs also are the natural extension of colorings for graphs. This filed has various applications (timetabling and scheduling problems, planning of experiments, multi-user source coding ect) and offers rich connections with other combinatorial areas (probabilis-tic methods extremal set theory, Ramsey theory, discrepancy theory etc). Thus many research results on the field have been obtained in last thirty years.In chapter one, we discuss the chromatic index of complete r-partitioned hypergraph. Let H be a hypergraph and endowed with a partition V₁,V₂,···,V_r of its vertex set V. Give a r-dimensional vector M = (p₁,p₂,···,p_r) where p₁∈N^*(1≤i≤r), the edge set of H is the every multiset E of V such that (|E∩V₁|,|E∩V₂|,···,|E∩V_r|)=M, then we call H the complete r-partitioned hypergraph, denoted by K_{n1,n2,···,nr}^M or K_{n1,n2,···,nr}^{p₁,p₂,···,p_r}. In this section we get four results and one conjecture.Theorem 1.2.1. Let H be r-partitioned hypergraph K_{n1,n2,···,nr}^{2,2,···,2} and suppose n₁≤n₂≤···≤n_r.If 2|n₁,we have q(H)=(n₁-1)(?)···(?);otherwise q(H) =n₁(?)···(?)Theorem 1.2.2. Let H be r-partitioned hypergraph K_{n1,n2,···,nr}^{t,t,···,t} with n₁≤n₂≤···≤n_r.For 1≤i≤r such that either t|n_i or (?)|(?),then we have q(H)=(?)(?)···(?)(?)^-1.Theorem 1.2.3. Let H be r-partitioned hypergraph K_{n1,n2,···,nr}^{t,t,···,t} with n₁≤n₂≤···≤n_r,for 1≤i≤r such that t (?) n_i and (?)(?)(?),then Theorem 1.2.4. Let H be r-partitioned hypergraph K_{n1,n2,···,nr}^{p₁,p₂,···p_r} with n₁≤n₂≤···≤n_r then we haveConjecture 1.2.1. Let H be r-partitioned hypergraph K_{n1,n2,···,nr}^{t,t,···,t} with n₁≤n₂≤···≤n_r,then q(H)=(?)···(?).Chapter two is devoted to studying the chromatic index of linear hypergraph. A hypergraph H = {E₁,E₂,···,E_m} is called linear,if i≠j then |E_i∩E_j|=(?).We call H linear hypertree, if H is a connected and acyclic linear hypergraph.In this section we get four results.Theorem 2.2.1. Let H be a loopless hypergraph on n vertices let S be the partial hypergraph determined by the edges of size at least 3. Ifâ–³_s=2, q(S) = 3, then q(H)≤n.Theorem 2.2.2. Let H be a loopless hypergraph on n vertices let S be the partial hypergraph determined by the edges of size at least 3. Ifâ–³_s≤3, q(S)≤3, then q(H)≤n.Theorem 2.2.3. Let H be a projective plane of rank r,then q(H)=r²- r+1.Theorem 2.3.1. Let H be a linear hypertree with maximum degree A, then q(H)=â–³.In chapter three, we study the edge-coloring with many components in path,θ-graph and T_i^*. Let H be a hypergraph. For a k-edge coloring c:E(H)→{1, 2,···,k}, let f(H,c) be the number of components in the subhypergraph induced by the color class with the least number of components. Let fk(H) be the maximum possible value of f(H, c) ranging over all k-edge colorings of H. In this section we get three results.Theorem 3.2.1. Let P_n be a path with n vertices,then f_k(P_n)=(?).Theorem 3.2.2. f(T_i^*)=(?)+1.(shown figure l(a))Theorem 3.2.3. Let G_θbeθ-graph,then f_k(G_θ)=2.(shown figure l(b))...