# Reduction of graph chromatic number to hypergraph 2-colorability

I'm following this paper titled "Coverings and colorings of hypergraphs" by Lovasz 1973, which is referenced in Garey and Johnson's Computers and Intractability, for the Set Splitting Problem. In this paper, the author tries to reduce graph chromatic number to hypergraph 2-colorability (same as set splitting).

You can find the paper here: http://web.cs.elte.hu/~lovasz/old-papers.html

I'm reproducing the reduction below.

Let $G$ be a graph, $V(G) = \{x_1,\dots,x_n\}$. Let $G_i$ be an isomorphic copy of $G$, $(i=1,\dots,k)$, $V(G_i) = \{x_{i,1},\dots,x_{i,n}\}$ ($x_{i,v}$ is a point corresponding to $x_v$). Take a new point $y$ and let $f_v = \{x_{1,v},\dots,x_{k,v},y\}$. Define hypergraph $H$ by $$H = E(G_1) \cup \dots \cup E(G_k) \cup \{f_1,\dots,f_n\}.$$ Then $H$ is 2-colorable if and only if $G$ is $k$-colorable. I don't understand this conclusion and the only example I've been able to come up with where this is true is $k = 1$.

• Dec 4, 2017 at 22:10

## 1 Answer

This is an error in Lovász' paper. However, a correct reduction is not too hard to come by. See this answer on math.se, in which a slight modification of the reduction you quote is shown to work.