Polychromatic Coloring Problem On Some Classes Of Hypergraphs

A hypergraph H=（V,E）consists of a vertex set V（H）=｛v1,v2,…,vq｝and a hyperedge set E（H）={e1,e2,…,en},where each hyperedge ei（?）V（G）,i=｛1,2,...,n}.Let m be a positive integer.A hypergraph H is m-colorable if it has a vertex-coloring with m colors which contains no monochromatic hyperedges.Specifically,when m=2,we call that hypergraph H is 2-colorable or has Property B.A polychromatic m-coloring of a hypergraph H is a coloring of vertices of H with m colors such that every hyperedge contains at least one vertex of each col-or.The polychromaic number of a hypergraph H is the maximum number m that H admits a polychromatic m-coloring.An r-balanced polychromatic coloring of a hypergraph H is a coloring of vertices of H such that every hyperedge contains at least r vertex of each color.On polychromatic coloring problem of hypergraphs,research focuses on two directions,one is to find better upper or lower bounds on polychromatic numbers of hypergraphs,the other is to determine the existence for r-balanced polychromatic colorings of hypergraphs for some positive integers r.Firstly,we study the balanced polychromatic colorings of some hypergraphs.We give several lower bounds on r-balanced polychromatic numbers for hypergraphs with n hyperedges.A 2ln n approximation to the number is obtained when r is a fixed positive integer.For the case that r=O（ln（n lnn））,there exists an O（ln n）ap-proximation algorithm;for the case that r=ω（ln（n ln n））,there exists a(2+3^1/2)r approximation algorithm.Also,we give a sufficient condition for a k-regular k-uniform hypergraph to have a balanced polychromatic coloring.For distinguished balanced polychromatic colorings,we show a sufficient condition for a hypergraph to have a 2-coloring such that a color appears at least d1 times and the other one appears at least d2 times on each hyperedges.Secondly,we discuss the problem of polychromatic edge coloring for subgraphs in a graph.At present,the research in this area focuses on the polychromatic edge coloring for subcubes in a hypercube and for factors in a complete graph.We study the polychromatic edge coloring for Hamilton cycles in a complete bipartite graph Kn,n,and determine that the polychromatic number is exactly n+1.This thesis is divided into four chapters.In Chapter 1,we mainly introduce the background and significance of the polychromatic colorings of hypergraphs and list the main results.In Chapter 2,we discuss the problem of balanced polychromatic coloring of hypergraphs.We give the proofs for the three results on bounds of bal-anced polychromatic number of hypergraphs.In Chapter 3,we discuss the problem of polychromatic edge coloring for subgraphs in a complete bipartite graph,and prove that the polychromatic number for Hamilton cycles in Kn,n is exactly n+1.In Chapter 4,we give some problems for further research.