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.

  • $\begingroup$ hbm answered the second part of the problem. Anyone knows, if I am right on my first answer? $\endgroup$ – knowKnothing Dec 16 '13 at 18:03
  • $\begingroup$ I am sort of confused on the boolean representation of a 4-colorable graph. Anyone? $\endgroup$ – 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.

So, the system has a solution if and only if the graph is bipartite. Deciding whether a graph is bipartite or not is polynomial.

  • $\begingroup$ 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? $\endgroup$ – knowKnothing Dec 16 '13 at 16:49
  • $\begingroup$ Yes. I'll fix it. $\endgroup$ – hbm Dec 16 '13 at 16:56
  • $\begingroup$ 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? $\endgroup$ – knowKnothing Dec 16 '13 at 17:14
  • $\begingroup$ If $(x_i - x_j)^2 = 1$, then either $x_i - x_j = 1$ or $x_i - x_j = -1$ $\endgroup$ – hbm Dec 16 '13 at 17:19
  • $\begingroup$ I agree. Why do you need to go around a cycle? I think it's the conversion from the satisfiability problem to the graph problem that I do not understand. You are comparing the equation to a graph problem and find a relation among +1 and -1 to the vertex possible coloring. Then, how do you know that there is a cycle? I know that if there is one, your properties are right. The cardinality of edges -1 and +1 are the same. Maybe, this is a construction that you derive from the similitude of the equation? $\endgroup$ – knowKnothing Dec 16 '13 at 17:36

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.