The hardness of 3-uniform hypergraph coloring
Irit Dinur, Oded Regev, Clifford Smyth · 2003
We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm (Krivelevich, Nathaniel, and Sudakov, 2001)colors such a graph using O(n/sup 1/5/) colors. Our result immediately implies that for any constants k > 2 and c/sub 2/ > c/sub 1/ > 1, coloring a k-uniform c/sub 1/-colorable hypergraph with c/sub 2/ colors is NP-hard; leaving completely open only the k = 2 graph case. We are the first to obtain a hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k /spl ges/ 4 such a result has been shown by Guruswami et al. (2000), who also discussed the inherent difference between the k = 3 case and k /spl ges/ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph (Kneser, 1955; Lovasz, 1978) and the Schrijver graph (Schrijver, 1978). We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has 'many' non-monochromatic edges.