[Math] Reduction of 3-SAT to 3-COLOR

computational complexitynp-complete

The decision version of the 3-COLOR problem is the problem of deciding whether an input graph G(V, E) can be colored using only 3 colors so that no 2 adjacent vertices have the same color.

I had interpreted that to mean that we were looking for any coloring.

However, most proofs I have seen that reduce 3-SAT to 3-COLOR to prove that 3-SAT is NP-Complete use subgraph "gadgets" where some of the nodes are already colored.
But in this case, it would only show that a specific 3-coloring (i.e. some nodes on the input graph are pre-colored) does not exist.

It doesn't show that no 3-coloring exists. Can someone clarify why the reduction is valid?

Best Answer

An important part of these gadget schemes is that there is a 3-clique somewhere called the palette that arbitrates the logic roles of colors. In other words, there are 3 nodes all connected to each other, labeled $v_T$, $v_F$, and $v_R$. The palette can be arbitrarily colored, and whatever colors are chosen represent the 3 logic values. Then when a gadget has a fixed "true" node in it, arcs are extended from fixed $v_F$ and $v_R$ nodes to it, to compel its color to be the same as $v_T$.

So the reduction doesn't require any strange modifications to the concept of the 3-COL problem. The reduction algorithm generates a planar graph, and that graph can be 3-colored iff the 3-SAT problem can be satisified.

Related Question