The hardness of 3-uniform hypergraph coloring (Q2368586)

Not much is known about the hardness of the problem of approximate coloring of a hypergraph. The paper makes a step towards better understanding of the problem by proving that coloring a 3-uniform 2-colorable hypergraph with \(c\) colors is NP-hard for any constant \(c\). The proof is based on combining the layered PCP and Kneser graph and relies on high chromatic numbers of the Kneser graph and its induced subgraphs known as Schrijver graphs.