---

3COL

a.k.a.

• 3-coloring

Define

… as a special case of COL with

Reduce

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

Perform a polynomial-time reduction using the graph below.

1. Create the first vertex colored 2.
2. Add 0/1 inputs for each variable.
3. Add 0/1 output.
4. For each clause:
   1. Add a new Or gadget.
   2. Connect the gadget to the appropriate inputs.
   3. Connect the gadget the 1 output.

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

The gadgets:

For example,

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

is reduced to:

Check

… that Or gadget implements the 3-way disjunction

\[\begin{equation*}
  \ell_1 \lor \ell_2 \lor \ell_3.
\end{equation*}
\]

The Or gadget:

No coloring exists when \(\ell_1 = \ell_2 = \ell_3 = 0\):

\(\ell_1\)	\(\ell_2\)	\(\ell_3\)	\(c_1\)	\(c_2\)	\(c_3\)	\(c_4\)	\(c_5\)
0	0	0	n/a	1	2	2	0
0	0	0	n/a	2	2	1	0
0	0	0	1	n/a	2	2	0
0	0	0	2	n/a	2	1	0
0	0	0	1	2	n/a	0	2
0	0	0	2	1	n/a	0	2
0	0	0	1	2	2	n/a	0
0	0	0	2	1	2	n/a	0
0	0	0	1	2	2	0	n/a
0	0	0	2	1	2	0	n/a

Otherwise, a coloring exists:

\(\ell_1\)	\(\ell_2\)	\(\ell_3\)	\(c_1\)	\(c_2\)	\(c_3\)	\(c_4\)	\(c_5\)
0	0	1	1	2	0	0	2
0	0	1	2	1	0	0	2
0	1	0	1	0	2	2	0
0	1	0	2	0	2	1	0
0	1	1	2	0	0	1	2
0	1	1	2	0	2	1	0
1	0	0	0	1	2	2	0
1	0	0	0	2	2	1	0
1	0	1	0	2	0	1	2
1	0	1	0	2	2	1	0
1	1	0	0	2	2	1	0
1	1	0	2	0	2	1	0
1	1	1	0	2	0	1	2
1	1	1	0	2	2	1	0
1	1	1	2	0	0	1	2
1	1	1	2	0	2	1	0