<p>$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 <a href="http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf">paper</a>.</p>

CC BY-SA 3.0
2015-11-07T21:14:43.340Z
2015-11-07T21:14:43.340Z
vb le
<p>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.</p>

<p>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?</p>

<cc.complexity-theory><reference-request><np-hardness><graph-colouring><hypergraphs>
NP-hardness of coloring uniform hypergraphs
John Machacek
# NP-hardness of coloring uniform hypergraphs

(Asked by: username_0 on 2015-11-07)

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?

**Tags:** cc.complexity-theory, reference-request, np-hardness, graph-colouring, hypergraphs


---

## 1 answers

### Answer by username_1 on 2015-11-07. Score: 13 | Accepted answer

$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](http://www.cs.elte.hu/~lovasz/scans/covercolor.pdf).


---

