Recall that a problem is NP-complete if it is both in NP and NP-hard. What properties must a reduction from 3SAT to 3-COLOR satisfy to prove NP-completeness?

In the OR-gadget construction, how do the "truth assignments" (color choices) for variables propagate to enforce the OR constraints of the 3SAT clauses?

Prove that the constructed graph for a given 3SAT instance is 3-colorable if and only if the 3SAT instance is satisfiable, carefully analyzing the role of the "gadget edges" in enforcing consistency.