98-31: Approximate Coloring of Uniform Hypergraphs

DIMACS TR: 98-31

Approximate Coloring of Uniform Hypergraphs

Authors: Michael Krivelevich and Benny Sudakov

ABSTRACT
We consider an algorithmic problem of coloring r-uniform hypergraphs. The problem of finding the exact value of the chromatic number of a hypergraph is known to be NP$hard, so we discuss approximate solutions to it. Using a simple construction and known results on hardness of graph coloring, we show that for any r\>= 3 it is impossible to approximate in polynomial time the chromatic number of r-uniform hypergraphs on n vertices within a factor n^{1-epsilon} for any epsilon>0, unless NP is a subset of ZPP. On the positive side, we present an approximation algorithm for coloring r-uniform hypergraphs on n vertices, whose performance ratio is O(n(loglog n)^2/(\log n)^2). We also describe an algorithm for coloring 3-uniform 2-colorable hypergraphs on n vertices in O(n^{9/41}) colors, thus improving previous results of Chen and Frieze and of Kelsen, Mahajan and Ramesh.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-31.ps.gz

DIMACS Home Page