# NP-hardness of coloring uniform hypergraphs

Since a $2$-uniform hypergraphs are just graphs. The problem of deciding if $2$-uniform is $k$-colorable for $k=1,2$ is easy, and NP-hard for $k \geq 3$ colors. This is well know and I have seen proofs in many places.

The situation changes if we look at $s$-uniform hypergraphs for $s \geq 3$, then the problem of deciding if an $s$-uniform hypergraph is $2$-colorable becomes NP-hard. I have read this fact multiple places, but without reference. What is the reference for classifying when the problem of deciding if an $s$-uniform hypergraph is $k$-colorable is NP-hard?

$2$-coloring $s$-uniform hypergraphs is also called Set Splitting, problem [SP4] in Garey-Johnson book. The hardness proof is due to Lovasz in this paper.