1
$\begingroup$

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.

$\endgroup$
6
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 6, 2021 at 17:22
  • $\begingroup$ Can you give a self-contained definition of the "triangle-free 3-colorability" problem? $\endgroup$
    – D.W.
    Jan 6, 2021 at 19:31
  • $\begingroup$ Presumably, 3-colorability of triangle-free graphs. $\endgroup$ Jan 6, 2021 at 20:29
  • $\begingroup$ Yes, as Yuval stated, triangle-free 3-colorability is simply the problem of 3-colorability on graphs that contain no triangles. $\endgroup$
    – kolomann
    Jan 6, 2021 at 21:00
  • $\begingroup$ The proof here is a one paragraph gadget reduction. $\endgroup$ Jan 7, 2021 at 10:23

1 Answer 1

1
$\begingroup$

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'$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.