Reduction of graph chromatic number to hypergraph 2-colorability

Question

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_{iv}$ 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$.

Answer 1

As the other answer points out, the reduction in the original paper seems to have a bug: $H$ will not be two-colorable unless $G$ is bipartite. I couldn't quite see how to prove the reduction in the other answer works, but here is one that I think does.

The vertices of $H$ will be $\{x_{i, v}: i \in [k], v \in V(G)\} \cup \{z\}$. $H$ has an edge $f_v = \{x_{1,v}, \ldots, x_{k,v}\}$ for every $v \in V(G)$, and, for each $(u,v) \in E(G)$, and each $i \in [k]$, an edge $\{z, x_{i,u}, x_{i,v}\}$.

Given a coloring $\chi_G:V(G) \to [k]$ of $G$ you can construct a $2$-coloring $\chi_H:V(H) \to \{0,1\}$ of $H$ by setting

$$ \chi_H(z) = 1,\\ \chi_H(x_{i,v}) = 1 \iff \chi_G(v) = i. $$

It's easy to check that no edge of $H$ is monochromatic.

In the other direction let $\chi_H$ be a proper 2-coloring of $H$, and assume that $\chi_H(z) = 1$. (If this is not the case just rename the colors.) Since no edge $f_v$ is monochromatic, for every $v \in V(G)$ there is some $i$ such that $\chi_H(x_{i,v}) = 1$. Pick an arbitrary such $i$ and set $\chi_G(v) = i$. This is a proper coloring, or otherwise there would be an $i \in [k]$ and an edge $(u,v) \in E(G)$ such that $\chi_H(x_{i,u}) = \chi_H(x_{i,v}) = 1$, which would make the edge $\{z, x_{i,u}, x_{i,v}\}$ of $H$ monochromatic.

Answer 2

I don't think this is true as stated, since if $(u,v)$,$(u,w)$,$(v,w)$ is a triangle in $G$ then clearly there is no way to "two color" the corresponding hyper edges in $H$ no matter how many isomorphic copies of $G$ you make, yet, $G$ may still be $k$-colorable for $k>2$.

Here is a different way that may work. Following your same set up, Let $e^{H}_{u,v}= {\{ x_{1,u},x_{1,v},x_{2,u},x_{2,v},\dots ,x_{k,u},x_{k,v} }\}$ and let $$E(H)= (\bigcup_{(u,v)\in E(G)} e^{H}_{u,v}) \cup {\{f_1,\dots ,f_n}\}$$

If $G$ is $k$-colorable, with $c:V \rightarrow [k]$ as the coloring, then for each $j\in[k]$, and for each vertex in $c(j)^{-1}$, color it's copy in $G_j$ green, and the rest of the vertices in that copy red. This is clearly a two coloring of $H$ since we have ensured that for every vertex, it is colored green in at least one copy $G_i$, and for any edge $(u,v)\in E(G)$, the color of $x_{j,u}$ is not the same as the color $x_{j,v}$ for some $j \in [k]$. Note that we didn't need to use the $f_i$'s here.

For the other direction, this was the best start I could get... Assume that we have a $2$-coloring of $H$, by having the same element $y$ in each $f_i$ we know that for no two distinct vertices $u$ and $v$ did our $2$ coloring assign green to $x_{j,v}$ and red to $x_{j,u}$ for all $j\in[k]$. This is because we have to color $y$ red or green, and y appears in $f_u$ and $f_v$. This implies that if $x_{j,v}$ is colored say, red, for all $j$ and $x_{j,u}$ is also colored red for all $j$, then $u$ and $v$ are not adjacent (o.w. we couldn't color $e^{H}_{u,v}$). I am stuck here. Somehow you need to construct a $k$-coloring of $G$, but it's not clear how. I hope this helps (I would have left as a comment, but it's too long).