4
$\begingroup$

This problem is related to ”Normal coloring of cubic graphs (part 1) - a previous post. We repeat the definitions, slightly modified so as to get to the point (we define normal edge 5 colorability, rather than the more general normal edge $k$ colorability).

Definition A normal edge 5 coloring (or normal 5 coloring) of a cubic graph $G$ is a proper coloring of the edges with 5 colors, so that for any edge $e\in E(G)$, the four edges adjacent to $e$ are colored with two colors, or with four colors.

Thus, an edge $e$ and its four adjacent edges might utilize three colors, or five colors.

If three colors are used, $e$ is called poor, and if five colors are used, $e$ is called rich.

...

Question I would like to know how to transform an instance of this problem to a CNF formula. That is, given a graph $G$, produce a CNF formula, such that a satisfying assignment can be translated back to a normal 5 coloring of the graph.

Note that working with the line graph of the cubic graph, as one would in dealing with a typical edge coloring problem, is a bit tricky (and that is all I dare to say).

Please advise if this question would be better off if posted in the theoretical computer science pages. Thanks in advance.

$\endgroup$
4
$\begingroup$

Start with $5|E(G)|$ variables $x_{e,i}$, one for each $e \in E(G)$ and $i \in \{1,2,3,4,5\}$. Intuitively $x_{e,i}$ means that edge $e$ is colored with color $i$.

A CNF formula $\phi$ can be obtained by the logical and of the following sub-formulas.

Each edge must have exactly one color:

  • At least one color, for each $e \in E(G)$: $(x_{e,1} \vee x_{e,2} \vee x_{e,3} \vee x_{e,4} \vee x_{e,5})$

  • At most one color, for each $e \in E$, and $i,j \in \{1,2,3,4,5\}$ with $i<j$: $(\overline{x_{e,i}} \vee \overline{x_{e,j}})$

The coloring must be proper:

  • For each pair $e,f \in E(G)$ of adjacent edges and for each $i \in \{1,2,3,4,5\}$: $(\overline{x_{e,i}} \vee \overline{x_{f,i}} )$

If $e=(u,v)$ is an edge of $G$, let $f^e_1,f^e_2$ be the two edges other than $e$ that are incident to $u$, and $f^e_3,f^e_4$ be the two edges other then $e$ that are incident to $v$.

  • For each $e \in E(G)$ add a new variable $r_e$. This will encode "if $e$ is not rich, then $r_e$ is true": Notice that if $e$ is rich then $r_e$ can always be set to false. For every $i \in \{1,2,3,4,5\}$, every $j \in \{1,2\}$, and every $k \in \{3,4\}$: $(r_e \vee \overline{x_{f^e_j, i}} \vee \overline{x_{f^e_k, i}})$

  • For each $e \in E(G)$ add a new variable $p_e$. This will encode "if e is not poor, then p_e is true". Notice that if $e$ is poor then $p_e$ can always be set to false. For every ordered tuple $(j, k, h)$ of $3$ distinct elements from $\{1,2,3,4,5\}$: $( p_e \vee \overline{x_{f_1,j}} \vee \overline{x_{f_2,k}} \vee \overline{x_{f_3,h}}) \wedge ( p_e \vee \overline{x_{f_1,j}} \vee \overline{x_{f_2,k}} \vee \overline{x_{f_4,h}}) \wedge ( p_e \vee \overline{x_{f_1,j}} \vee \overline{x_{f_3,k}} \vee \overline{x_{f_4,h}}) \wedge ( p_e \vee \overline{x_{f_2,j}} \vee \overline{x_{f_3,k}} \vee \overline{x_{f_4,h}}) $

Finally, this will encode "e is rich or e is poor":

  • For every $e \in E(G)$: $(\overline{r_e} \vee \overline{p_e})$

If you have a satisfying truth assignment for $\phi$ then you can color edge $e \in E(G)$ with color $i$ iff $x_{e,i}$ is true.

If you have a coloring then let $c(e) \in \{1,2,3,4,5\}$ be the color of edge $e$. You an get a satisfying truth assignment for $\phi$ by setting:

  • $x_{e,c(e)}= \top$, and $x_{e,j} = \bot$ for $j \in \{1,2,3,4,5\} \setminus \{ c(e) \}$,
  • $r_e = \bot$ iff edge $e$ is rich,
  • $p_e = \bot$ iff edge $e$ is poor.
$\endgroup$
  • $\begingroup$ Thanks! Let me study this ... and will accept accordingly once I have digested it. I need to find some time later this week! $\endgroup$ – EGME Jun 27 at 8:05
  • $\begingroup$ Some typos and little things?: in the third to last bullet (top part), you need a clause for each color, right? Second to last, the list is 1,2,3,4,5 ... and also, (j,k,h) are distinct, right? Last, do you need to encode that each edge is rich or poor but not both? $\endgroup$ – EGME Jun 27 at 8:41
  • $\begingroup$ Third to last bullet: that's correct. I fixed it. Second to last bullet: ooops, I wrote $\{1,2,3,3,5\}$ by mistake. Those are indeed all possible ways of selecting 3 distinct elements from that set, where order matters. $\endgroup$ – Steven Jun 27 at 11:58
  • $\begingroup$ Thanks! It seems this will work! $\endgroup$ – EGME Jun 27 at 12:00
  • $\begingroup$ "e is not simultaneously rich and poor" translates to $\overline{(\overline{p_e}\wedge\vee\overline{r_e})}=(p_e \vee r_e)$, which is always true in any satisfying assignment. Suppose towards a contradiction that, in a satisfying assignment, $p_e=r_e=\bot$. $r_e=\bot$ implies that, for every pair of distinct edges in $ \{f^e_1,f^e_2,f^e_3,f^e_4\}$, those edges have different colors. I.e., $f^e_1,f^e_2,f^e_3,f^e_4$ all have different colors. Also, $p_e=\bot$ implies that there is no way to find $3$ distinct edges in $\{f_1,f_2,f_3,f_4\}$ having different colors. Hence the contradiction. $\endgroup$ – Steven Jun 27 at 12:11

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.