## 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