2
$\begingroup$

I am trying to tackle a specific problem so any help would be greatly appreciated:

Let $G = (V,E)$ be an undirected graph with vertex set $V$ and edge set $E$. A 3-coloring of $G$ is a map $\chi:V\to \{R,G,Y\}$ such that if $\{x,y\}\in E$ then $\chi(x)\neq \chi(y)$. (Let $R,G,Y$ stand for red, blue, and yellow respectively).

Suppose $n > 1$ and let $V_n = \{0,1,\cdots,n-1\}$ and let $G_n = (V_n,E_n)$ be an undirected graph with vertex set $V_n$. For each $i$, $0 \leq i < n$ let $R_i,B_i,Y_i$ be propositional variables. We can think of $i$ being a node so $R_i$ says node $i$ has a color of red.

Give a propositional formula $A_n$ using the variables $\{R_i,B_i,Y_i | 0 \leq i < n\}$ such that $A_n$ is satisfiable iff $G_n$ has a 3-coloring. Do this in such a way that $A_n$ can be computed efficiently from $G_n$ (e.g. don't define $A_n$ to be $R_1$ if $G_n$ has a three coloring and ($R_1 \wedge \neg R_1$) otherwise).

My inclination for a question like this is to set up some sort of CNF formula, that is come up with a set of clauses that set out to take care of different properties. For instance I believe for something like this I need a clause that deals with the case that every node has a color, maybe one that deals with every node cannot have more than one color, and that every node cannot be the same color as an adjacent node? I am not really sure how to illustrate that last one or if there are cases that I am missing.

$\endgroup$
  • $\begingroup$ What have you tried? Have you written down the requirements for a node labelling to be a 3-coloring? Have you tried translating those requirements into logic? Which ones did you run into problems with? $\endgroup$ – D.W. Apr 20 '14 at 22:07
1
$\begingroup$

Hint: Try to formalize the following:

  1. Every node has at least one color.
  2. Every node has at most one color. (This is actually not necessary.)
  3. Any two adjacent nodes cannot have the same color.

Another hint:

The first can be formalized as $R_i \lor B_i \lor Y_i$ for all $i$.

$\endgroup$

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.