Normal colorings of cubic graphs to SAT

Question

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.

Answer 1

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.