# 3-Colorability Graph Questions

I know that a boolean formula for 3-colorability is : $\wedge_{i \in Vertices}(\bar{b_{i,1}} \vee \bar{b_{i,2}}) \wedge_{\left(i < j \right)\in Edges} ((b_{i,1} \bigoplus b_{j,1}) \vee (b_{i,2} \bigoplus b_{j,2}))$

I also know that there's a "reduction" that can be made from 3-colorability to 4-colorability. This reduction is done by adding one extra vertex of one unique color and adding and attaching an edge for every vertex in a 3-color graph to this new vertex. However, I am sort of confused on how to apply it this concept into the boolean formula above.

• How do I write a boolean formula for a 4-colorability graph? Can I just do this? $\wedge_{i \in Vertices}( \bar{b_{i,3}} \vee \bar{b_{i,1}} \vee \bar{b_{i,2}}) \wedge_{\left(i < j \right)\in Edges} ((b_{i,1} \bigoplus b_{j,1}) \vee (b_{i,2} \bigoplus b_{j,2} ) \vee (b_{i,3} \bigoplus b_{j,3}))$

I have expanded the 3-colorability formula and expressed it in truth table form.

$\bar{b_{i,1}} \vee \bar{b_{i,2}} =$ [1 1 1 0]

$(b_{i,1} \bigoplus b_{j,1})$ = [0 1 1 0] and the other $\bigoplus$ would be the same. Then, the disjunction of these $\bigoplus$ is the same [0 1 1 0]

I end up with:

$\wedge_{i \in Vetices}$ [0 1 1 1] $\wedge_{(i<j) \in Edges}$ [0 1 1 0]

How do I proceed given the concept I wrote above of 4-colorability?

• The 3-colorability problem is NP-Complete and can be reduce to 3-Sat problem. Also, it can be shown as the following decision problem:

Does the system of equations

$[(x_{i} - x_{j})^{2} = 1]_{mod 3} : (i<j) \in Edges,$ have a solution $x_{i} \in \{0,1,2\}; 1\leq i \leq n.$

We know that this problem is NP-Complete.

Give and justify a polynomial time algorithm for the following decision problem: Does the system of equations $(x_{i} - x_{j})^{2} = 1 : (i,j) \in Edges,$ have a real solution?

It seems like a Gaussian elimination problem, but I am not fully sure how to start attacking it. Any ideas? Thank you.

• hbm answered the second part of the problem. Anyone knows, if I am right on my first answer? – knowKnothing Dec 16 '13 at 18:03
• I am sort of confused on the boolean representation of a 4-colorable graph. Anyone? – knowKnothing Dec 17 '13 at 11:37

Suppose you have a solution to the system of equations. Now, color the edge $(i,j)$ by color $x_j - x_i$ if $i \lt j$ and $x_i - x_j$ otherwise. Note that all the edges will be colored either $1$ or $-1$. Also, notice that the sum of colors of the edges of any cycles must be $0$. As you move from one vertex to the next in the cycle, you get the color of the next vertex by either adding $1$ or $-1$ to the color of the current vertex. Since going around the cycle brings you back to the same place, then the number of edges of color $1$ is the same as the number of edges of color $-1$. Hence the cycle must be of even length and the graph must be a bipartite graph.
• Thank you for trying to help. You mean on your second sentence that color the edge (i,j) by color $x_{j}- x_{i}$ if $i<j$ and $x_{i} - x_{j}$otherwise, right? – knowKnothing Dec 16 '13 at 16:49
• I am trying to interpret your solution and the question. Why are you coming up with 1 or -1 ? I realize that 1 or -1 to the square give 1, is this why? Also, -1 and 1 could be equal to $x_{i}- x_{j}$ and $x_{j} - x_{i}$. Why do you need to go around in a cycle? – knowKnothing Dec 16 '13 at 17:14
• If $(x_i - x_j)^2 = 1$, then either $x_i - x_j = 1$ or $x_i - x_j = -1$ – hbm Dec 16 '13 at 17:19