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.
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.
So, the system has a solution if and only if the graph is bipartite. Deciding whether a graph is bipartite or not is polynomial.