Reduction of 3-SAT to 3-COLOR

Question

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?

Answer 1

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.

Answer 2

To understand the proof, we must remember that in an unsatisfiable 3CNF formula it is impossible for all the clauses to be false at the same time and therefore they can not be colored with the same color. The only case where the clauses have the same truth value is when the formula is satisfiable. In this case all the clauses are true. In other words, if we can color the outputs of all the gadgets with the same color (whatever that color is), the formula 3CNF is necessarily satisfiable