---

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

\[\begin{equation*}
  F
  = c_1 \land c_2 \land \cdots
  =
  (\ell_{11} \lor \ell_{12} \lor \ell_{13})
  \land
  (\ell_{21} \lor \ell_{22} \lor \ell_{23})
  \land
  \cdots,
\end{equation*}
\]

connect the graph

For example,

\[\begin{equation*}
  F
  =
  (\lnot x_1 \lor x_2 \lor \lnot x_2)
  \land
  (\lnot x_2 \lor x_3 \lor \lnot x_3)
\end{equation*}
\]

reduces to the graph