# NPC-problem reduction to triangle-free 3-colorability

lately, I have encountered a problem that I struggle to find a satisfactory solution for. I need to prove that triangle-free 3-colorability is NP-complete. Therefore I assume the right way is to find an NP-complete problem and reduce it to my problem.

I tried it with general 3-colorability, but I was unable to create function F() that would reduce a general graph to a triangle-free graph without changing its colorability.

Is it a good direction? Does it make sense to reduce the 3-colorability problem?

If yes, I would appreciate any advice on how to finish the proof. If I am doing it wrong, I would appreciate any advice on the reduction.

• Where have you encountered this problem? I am familiar with a paper that proves hardness of this problem by a reduction from 3-color. It is a bit challenging, perhaps there are easier reductions, I'm not sure though. Jan 6, 2021 at 17:22
• Can you give a self-contained definition of the "triangle-free 3-colorability" problem?
– D.W.
Jan 6, 2021 at 19:31
• Presumably, 3-colorability of triangle-free graphs. Jan 6, 2021 at 20:29
• Yes, as Yuval stated, triangle-free 3-colorability is simply the problem of 3-colorability on graphs that contain no triangles. Jan 6, 2021 at 21:00
• The proof here is a one paragraph gadget reduction. Jan 7, 2021 at 10:23

We reduce from 3-coloring, following Kráľ, Kratochvíl, Tuza and Woeginger, Complexity of Coloring Graphs without Forbidden Induced Subgraphs. We will need to use a gadget $$H$$, with the following properties:

• $$H$$ is a 3-colorable triangle-free graph.
• There are two vertices $$a,b \notin H$$, not connected by an edge, such that any 3-coloring of $$H$$ gives $$a,b$$ different colors.

Given such a gadget $$H$$, here is how to reduce 3-coloring to triangle-free 3-coloring. We start with a graph $$G$$. We construct a new graph $$G'$$ as follows. The graph $$G'$$ will have all vertices of $$G$$, together with some new vertices. For each edge $$e = (x,y) \in G$$, there is a copy $$H_e$$ of $$H$$. We identify $$a_e$$ (the copy of $$a$$ in $$H_e$$) with $$x$$, and $$b_e$$ with $$y$$. This completes the construction.

The new graph is triangle-free. Indeed, suppose that it contained some triangle $$u,v,w$$. Since the vertices $$u,v$$ are connected, they must reside in some copy $$H_e$$ of $$H$$. Since $$(a,b) \notin H$$, at least one of these vertices doesn't belong to $$V$$, say $$u \notin V$$. Since all neighbors of $$u$$ are in $$H_e$$, it follows that $$u,v,w$$ all reside in $$H_e$$, contradicting the triangle-freeness of $$H$$.

If $$G$$ is 3-colorable, then we can easily complete a 3-coloring of $$G$$ to a 3-coloring of $$G'$$ by using a 3-coloring of $$H$$ (by symmetry, it doesn't matter what colors $$a,b$$ get, as long as the colors are different). Conversely, the restriction of any 3-coloring of $$G'$$ to $$V$$ is a 3-coloring of $$G$$.

To complete the proof, we need to describe the gadget $$H$$. Our starting point is any critically 4-colorable triangle-free graph $$H'$$, such as the Grötzsch graph; here critically 4-colorable means that the graph is not 3-colorable, but becomes 3-colorable if we remove any edge.

We take any edge $$(a,c) \in H'$$ and replace it by an edge $$(b,c)$$, where $$b$$ is a new vertex (in particular, $$(a,b)$$ is not an edge). The resulting graph $$H$$ is still triangle-free. Since $$H'$$ was critically 4-colorable, the graph $$H$$ is 3-colorable: take a 3-coloring of $$H' \setminus \{(a,c)\}$$, and color $$b$$ appropriately. Any 3-coloring of $$H$$ must give $$a,b$$ different colors, since otherwise its restriction to all vertices but $$b$$ would be a 3-coloring of $$H'$$.