---

Reduce

… 3SAT to 3COL, showing NP-completeness of the latter.

Perform a polynomial-time reduction using the graph below.

1. Add three interconnected vertices, colored 1, 2, and 3.
2. For each variable, add two uncolored vertices connected to 2.
3. For each clause, add one Or gadget connected to:
   • the relevant variable vertices and
   • the vertex colored 1.

Given

$$F=c_1\wedge c_2\wedge \cdots =({\ell }_{11}\vee {\ell }_{12}\vee {\ell }_{13})\wedge ({\ell }_{21}\vee {\ell }_{22}\vee {\ell }_{23})\wedge \cdots ,$$

connect the graph

For example,

$$F=(\mathrm{\neg }{x}_1\vee x_2\vee \mathrm{\neg }{x}_2)\wedge (\mathrm{\neg }{x}_2\vee x_3\vee \mathrm{\neg }{x}_3)$$

reduces to the graph