TY - JOUR

T1 - The hardness of 3-uniform hypergraph coloring

AU - Dinur, Irit

AU - Regev, Oded

AU - Smyth, Clifford

PY - 2002

Y1 - 2002

N2 - We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm [20] colors such a graph using O(n1/5) colors. Our result immediately implies that for any constants k > 2 and c2 > c1 > 1, coloring a k-uniform c1-colorable hypergraph with c2 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 ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 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 [19,22] and the Schrijver graph [26]. 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.

AB - We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm [20] colors such a graph using O(n1/5) colors. Our result immediately implies that for any constants k > 2 and c2 > c1 > 1, coloring a k-uniform c1-colorable hypergraph with c2 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 ≥ 4 such a result has been shown by [14], who also discussed the inherent difference between the k = 3 case and k ≥ 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 [19,22] and the Schrijver graph [26]. 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.

UR - http://www.scopus.com/inward/record.url?scp=0036953855&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036953855&partnerID=8YFLogxK

U2 - 10.1109/SFCS.2002.1181880

DO - 10.1109/SFCS.2002.1181880

M3 - Article

AN - SCOPUS:0036953855

SN - 0272-5428

SP - 33

EP - 40

JO - Annual Symposium on Foundations of Computer Science-Proceedings

JF - Annual Symposium on Foundations of Computer Science-Proceedings

M1 - 6

ER -