Understanding 3-COLOR as NP-Complete: A Proof from Reductions and Gadget Usage

[JohnDoe2013]

The 3-COLOR decision problem is the problem of deciding whether a Graph G can be colored using only 3 colors such that no 2 adjacent nodes have the same color.

One way of proving that 3-COLOR is NP-Complete is to reduce from 3-SAT.
The reductions generally uses gadgets with 3 input nodes and one output node.
The key to the proof lies in proving that if all 3 input nodes are colored "FALSE", then no legal coloring exists where the output node is colored "TRUE" (however, it is possible to obtain a legal coloring where the output node is colored "FALSE").

This seems to me to be a reduction from 3-SAT to the problem of finding a SPECIFIC 3 COLORING of a graph as opposed to reducing to the problem of deciding whether a 3 COLORING exists. Is my understanding correct?

 

[Future Bruno]

No, your understanding is not correct. The reduction from 3-SAT to 3-COLOR is indeed a reduction to the problem of deciding whether a 3 COLORING exists. The gadgets with 3 input nodes and one output node are used to prove that if all 3 input nodes are colored "FALSE", then no legal coloring exists where the output node is colored "TRUE". This proves that for any 3-SAT instance, if the 3-COLOR problem is solvable, then the 3-SAT instance must also be satisfiable.