Transversal Of Hypergraphs

Hypergraph is generalization of general graph, coloring of general graph take an important part at graph theory. Now, It take form coloring theory. coloring of hypergraph, being generalization of coloring for general graph, its meanings are more profound, its contents are much rich, and its applications are more wide.In this paper, we discuss the coloring of hypergraph and obtain some relevant results.In Section One, we introduce general concepts and discuss why we research graph and hypergraph's coloring problem. Thus, we study the hypergraph coloring has inportant meaning.In Section Two, we investigate the relation between hypergraph polynomials and hypergraph coloring, using hypergraph polynomials depict hypergraph coloring.especially,we particularly study the 2-coloring hypergraph polynomials, obtain some sufficient and necessary conditions for hypergraph non- 2-coloring and sufficient conditions for hypergraph 2-coloring. Following, we get 2-coloring's sufficient conditions for the hypergraphs. Which edges are equal to vertices. last, from the meaning of hypergraph polynomials we obtain a maximum chromatic for general hypergraph. The main results in this part are follows:Proposition 2.2. H is not 2-colorable, then p(H) =0 for all x_i∈{0,1}.Proposition 2.3. If some coefficient of q(H)(?)0(modk_i) (i=1,2,···,t), then H is 2-colorable.Theorem 2.1. If perm(M)(?)0(modk_i)(i =1,2,···,t), then H is 2-colorable.Theorem 2.2. If for any i,∑_j=1ⁿ|E_j\{i}|perm M_ji(?)(mod 2 k_i), then H is 2-colorable.Theorem 2.3. Let H be a simple hypergraph, then x(H)≤S+1.In Section Three,we investigate the relation between Local Lemma and hypergraph coloring and use the lopsided version of the Local Lemma to give some sufficient conditions on hypergraph t-coloring, as well as 2-coloring such that each edge contains at least 2 points of each color and generalize it to t-coloring. The main results in this part are follows:Theorem 3.3. Let H be a hypergraph in which every edge contains at least k points and meets at most d other edges. Let t≥2 be an integer. If e((d+1)(t-1)+1)t^-k≤1, then H has a t-coloring.Theorem 3.4. Let H be a hypergraph in which every edge contains at least k points and meets at most d other edges. Let t≥2 be an integer. If e((d+1)(t-1)+1)(1-1/t)^k≤1, then H has a t-coloring in which each color appears on each edge.Theorem 3.5. Let H be a hypergraph in which every edge contains at least k (k≥4) points and meets at most d other edges. If e(k+1)2^-k(d+2)≤1, then H has a 2-coloring such that each edge contains at least 2 points of each color.Generalisation. Let H be a hypergraph in which every edge contains at least k (k≥2t) points and meets at most d other edges. Let t≥2, If e(1-1/t)^k-1(1-1/t+k/t)(d+2)≤1, then H has a t-coloring such that each edge contains at least 2 points of each color.In Section Four, we investigate some patter to structure some complex hypergraphs. For some we get their exact chromatic number, for others we only get their maximum chromatic. The main results in this part are follows: proposition 4.1. Let H₁ and H₂ be two hypergraphs, and x(H₁)=λ₁,x(H₂) =λ₂. then x(H₁+H₂)=maxP{λ₁,λ₂}.proposition 4.2. Let H₁ and H₂ be two hypergraphs, and x(H₁)=λ₁,x(H₂)=λ₂. then x(H₁(?)H₂)=2.proposition 4.3. Let H₁ and H₂ be two hypergraphs, and x(H₁)=λ₁,x(H₂)=λ₂. then x(H₁∪H₂≤λ₁·λ₂.proposition 4.4. Let H₁ and H₂ be two hypergraphs, and x(H₁)=λ₁,x(H₂)=λ₂. then x(H₁·H₂)≤min{Aλ₁·λ₂}.Definition 4.5. The hyper graph product H₁×H₂ of H₁ and H₂ is the hyper graph with vertices of V(H₁)×V(H₂) and the edge set E={e×f:e∈E(H₁),f G∈(H₂)}, where×denotes the usual Cartesian product of sets.In Section Four, we study The propositions of strong coloring of hypergraph and get the chromatic of some concrete hypergraphs (i.e egl-eg5). Also propose some questions to further study the strong coloring of hypergraph.