TAOCP 7.2.2.2 Exercise 176
You've hit your limit.
Section 7.2.2.2: Satisfiability
Exercise 176. [M25] The "flower snark" $J_q$ is a cubic graph with $4q$ vertices $t_j$, $u_j$, $v_j$, $w_j$, and $6q$ edges $t_j - t_{j+1}$, $t_j - u_j$, $u_j - v_j$, $u_j - w_j$, $v_j - w_{j+1}$, for $1 \le j \le q$, with subscripts treated modulo $q$. Here, for example, are $J_5$ and its line graph $L(J_5)$:
$$J_5 = \raisebox{-0.5ex}{\includegraphics[height=8ex]{j5.png}} \qquad L(J_5) = \raisebox{-0.5ex}{\includegraphics[height=8ex]{lj5.png}}$$
a) Give labels $a_j$, $b_j$, $c_j$, $d_j$, $e_j$, and $f_j$ to the edges of $J_q$, for $1 \le j \le q$. (Thus $a_j$ denotes $t_j - t_{j+1}$, and $b_j$ denotes $t_j - u_j$.) What are the edges of $L(J_q)$? b) Show that $\chi(J_q) = 2$ and $\chi(L(J_q)) = 3$ when $q$ is even. c) Show that $\chi(J_q) = 3$ and $\chi(L(J_q)) = 4$ when $q$ is odd. Note: Let $fsnark(q)$ denote the clauses (15) and (16) that correspond to 3-coloring $L(J_q)$, together with the $b_{1,4} \wedge c_{1,2} \wedge d_{1,3}$, to set the colors of $(b_1, c_1, d_1)$ to $(1, 2, 3)$. Also let $fsnark'(q)$ denote $fsnark(q)$ augmented by (17). These clauses make excellent benchmark tests for SAT solvers.
Verified: no
Solve time: 3m45s
You've hit your limit. Please try again later.