On The Polychromatic Colorings And Monochromatic Path Patitions In The Hypergraphs

Let H be a hypergraph,If H=（V（H）,E（H））,|V（H）|=n,and,for every k vertices v₁,V₂,…,Vk∈V（H）,{v₁,V₂,…,v_k}=e ∈ E（H）,then we say that hypergraph H is a complete k-uniform hypergraph,denoted by k_n^（k）.We denote a complete 3-partite 3-uniform hypergraph by K_n1,n2,n3^（3）,if |V₁|=n₁,|V₂|=n₂,|V₃|=n₃,（?）V_i=V（H）,V_i∩V_j=（?）,for all 1≤i≤j≤3 and each hyperedge uvw ∈ E（H）has u ∈ V₁,v ∈V₂,ω∈V₃.Let m be a positive integer.A hypergraph H is m-colorable if it has an m-coloring of the vertices with no monochromatic hy-peredges.Specifically,if m=2 then hypergraph H is 2-colorable or has Property B.An m-coloring of the vertices of a hypergraph is a polychromatic m-coloring if every hyperedge contains at least one vertex of each color.It is noteworthy that if a hypergraph has a polychromatic m-coloring,then it has a polychromatic l-coloring,where 1 ≤l ≤m.Firstly,We study the polychromatic coloring of a hypergraph,which is a generalization of 2-coloring（Property B）of a hypergraph.We are interested in two problems:（1）how large m could be if we want a hypergraph to have a polychromatic m-coloring?（2）how to obtain an "equitable" polychromatic coloring of a hypergraph?We obtain two results on polychromatic colorings of hyper graphs,which improve some previous results.The dual of a hypergraph H=（V,E）with V={X₁,x₂,...,x_n},E={Y_i,Y₂,...,Y_m} is a hypergraph H^*whose vertices y₁,y₂,…,y_m correspond to the hyperedges of H,and whose hyper-edges Xi={y_j|x_i ∈ Y_j},i=1,2,...,n.A polychromatic m-coloring of H^*corresponds to a cover m-decomposition of H.So the results on polychromatic m-colorings can be stated in the dual.Secondly,we study 2-edge-colorings of hypergraphs.Traditionally,the colors of a 2-edge-coloring always mean red and blue.At present,it’s relatively rare for the result on monochromatic loose-path partitions in 2-edge-colorings of hypergraphs.The previous conclusions are mainly on complete k-uniform hypergraphs.In this thesis,we firstly study the problem on monochromatic loose-path partitions in ev-ery 2-edge-coloring on balanced complete 3-partite 3-uniform hypergraphs.This will lay a foundation for future research on the general monochromatic partitions problems in 2-edge-colorings of k-partite k-uniform hypergraphs.The thesis consists of four chapters.In Chapter 1,we mainly introduce the background and significance of graph and hypergraph coloring problems,the pati-tion problems of hypergraphs,give some basic concepts and symbols to be used in this thesis,expound research progress on the colorings and monochromatic patitions theory on hypergraphs and list our main results in this thesis.In Chapter 2,we study the polychromatic colorings and the cover m-decompositions of hypergraph-s.In Chapter 3,we study the monochromatic loose-path patitions of complete 3-partite 3-uniform hypergraphs.In Chapter 4,we indicated some problems for further research.