3-COLOR Decision Problem

Question

The 3-COLOR problem takes as input a graph and decides whether it can be colored using only 3 colors so that no 2 adjacent nodes have the same color.

The reduction from 3-SAT to 3-COLOR uses the following gadget (see below) to represent a clause in the 3-SAT formula.

It is clear that a valid 3-coloring exists only when at least one of x, y, or z has the same color as T. Now, suppose all 3 literals are False. Then, if the x, y and z nodes are colored the same as the F node, there is no valid 3-coloring.

However, to the 3-color algorithm, the gadget is just a subgraph. Even if x, y and z are False, if we color them the same as the T node, there would be a valid coloring. It's not clear to me that you can specify in the input to the 3-color algorithm that if a literal is False/True, it should have the same color as F/T.

So, how is the reduction valid?

Answer 1

Actually, there is no 3-coloring if the 3 literals are colored as F. This is because the node after the "merge" will be colored as F, while the blank below left of T will be as X. The remaining node (upper left of T) can have no valid color in this case.

Answer 2

For each variable y, build two vertices, one for y and one for ~y. Connect both y and ~y to X, the unique global node that is connected in a triangle with T(rue) and F(alse). These connections will ensure that one of {y,~y} gets a color of T and the other gets a color of F. This is what gives you the connection between a coloring and a truth assignment.

Then you use the gadget to connect each clause in the 3-SAT formula, using the right literal vertices. Each gadget connects to the same global T as shown in the picture.