# 3 Colorability reduction to SAT

I'd like to reduce 3 colorability to SAT. I've stuffed up somewhere because I've shown it's equivalent to 2 SAT.

Given some graph $G = (V,E)$ and three colors, red, blue, green. For every vertex $i$, let the boolean variable $i_r$ tell you whether the $i$-th vertex is red (or more precisely, that the $i$-th vertex is red when $i_r = 1$). Similarly, define $i_b$ and $i_g$.

Suppose two vertices $i$ and $j$ were connected by an edge $e$. Consider the clause \begin{align} (\bar i_r \vee \bar j_r) \end{align} If we demand the clause is true, it means that the vertices cannot both be red at the same time. Now consider the bigger clause $\phi_e$ \begin{align} (\bar i_r \vee \bar j_r)\wedge(\bar i_b \vee \bar j_b)\wedge(\bar i_g \vee \bar j_g) \end{align} which, if true, demands that the vertices $i$ and $j$ aren't both the same color. By itself, this clause is in 2-SAT.

For every edge $e \in E$, I now make a clause $\phi_e$ of the above form and put them all together using $\wedge$'s \begin{align} \phi = \wedge_{e \in E} \phi_e \end{align} Thus, for the entire graph, I've come up with a 2SAT formula which is equivalent to 3 coloring.

This is obviously wrong, but I can't tell where I've screwed up.

• How do you make sure that every node gets a color? – adrianN Jul 4 '13 at 11:40
• As @adrianN says, consider the assignment $\alpha(i_r) = \alpha(i_g) = \alpha(i_b) = \bot$ for all $i \in V$. – Pål GD Jul 4 '13 at 12:07

With your modeling, setting $i$, $i_r$, $i_g$ and $i_b$ to false for all vertices yields a solution of the SAT problem and this is not a solution of the graph coloring problem.
You need to add clauses to say that each vertex is blue or green or red, namely $(i_r\vee i_g\vee i_b)$. Then it becomes a 3-SAT problem.
• Thanks @adrianN and A.Schulz. I see what I'm missing. Here's what I still do not understand. The statement $\phi$ that I've got above is 2SAT. I will have to add the clauses $(i_r \vee i_g \vee i_b)$ to $\phi$ for every vertex $i$, each of which is 3SAT. However, the statement $\phi$ itself is only 2SAT and by adding the above statements, I'll have a mixture of 2SAT and 3SAT statements. I know how to 'dilate' all 2SAT clauses in $\phi$ to 3SAT by adding dummy variables. That is what I have to do to make the entire coloring problem 3SAT, correct? – WiFO215 Jul 4 '13 at 16:22
• Actually, you don't need any dummy variable: any 2-clause $(\overline{i_b}\vee\overline{i_g})$ can be extended to an equivalent 3-clause $(\overline{i_b}\vee\overline{i_g}\vee\overline{i_g})$ by duplicating one litteral. – Emeu Jul 6 '13 at 8:59