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.

  • 2
    $\begingroup$ How do you make sure that every node gets a color? $\endgroup$
    – adrianN
    Jul 4 '13 at 11:40
  • $\begingroup$ As @adrianN says, consider the assignment $\alpha(i_r) = \alpha(i_g) = \alpha(i_b) = \bot$ for all $i \in V$. $\endgroup$
    – 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.

Note that if a vertex is assigned to more then one color, then we can take any of its colors and obtain a 3-coloring.

  • $\begingroup$ 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? $\endgroup$
    – WiFO215
    Jul 4 '13 at 16:22
  • $\begingroup$ 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. $\endgroup$
    – Emeu
    Jul 6 '13 at 8:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.