Section 7.2.2.2: Satisfiability

Exercise 19. ▶ [29] [29] Continuing exercise 17, let $h(n)$ be the largest number of regions that can be given two colors simultaneously (without using the clauses (17)). Investigate $h(n)$.

Verified: no
Solve time: 2m15s

---

$$ \text{Let }N=n(n+1) $$

be the number of vertices of McGregor’s graph of order $n$. We want the maximum number of vertices that may be assigned two colors at the same time in a proper four-coloring, without imposing the clauses (17) that force each vertex to receive exactly one color.

For a vertex $x$, introduce the four Boolean variables

$$ v_1(x),v_2(x),v_3(x),v_4(x), $$

where $v_i(x)$ means that $x$ receives color $i$. The ordinary coloring constraints from exercises 15, 17 ensure that adjacent vertices cannot have the same color. The clauses (17) are the constraints

$$ v_1(x)+v_2(x)+v_3(x)+v_4(x)=1, $$

so removing them permits a vertex to have several colors. To count vertices having more than one color, introduce a new variable $v_x$ for each vertex $x$, intended to mean that $x$ receives at least two colors.

The condition that $x$ has at least two colors is equivalent to saying that not exactly one of the four variables $v_i(x)$ is true. In conjunctive normal form this is expressed by

$$ (v_1(x)\vee v_2(x)\vee v_3(x)\vee \neg v_x) $$

$$ \wedge, (v_1(x)\vee v_2(x)\vee v_4(x)\vee \neg v_x) $$

$$ \wedge, (v_1(x)\vee v_3(x)\vee v_4(x)\vee \neg v_x) $$

$$ \wedge, (v_2(x)\vee v_3(x)\vee v_4(x)\vee \neg v_x). $$

Indeed, if $v_x$ is true, then every one of the four clauses requires that at least one of the three colors different from the omitted color is present. Hence a single true color variable cannot satisfy the clauses, and therefore at least two colors must be assigned. Conversely, if at least two colors are present, all four clauses are satisfied.

The optimization problem is therefore equivalent to finding the largest possible number of variables $v_x$ that can simultaneously be true. This can be tested by adding the symmetric threshold constraint

$$ S_{\ge r}(v_{x_1},v_{x_2},\ldots ,v_{x_N}), $$

which requires at least $r$ of the $v_x$'s to be true. The resulting formula is satisfiable exactly when

$$ h(n)\ge r . $$

The four colors are symmetric, so only one assignment of colors to the vertices of the unique $4$-clique needs to be fixed in order to break the color symmetry.

Applying this construction gives the following exact values for the small orders:

$$ \begin{array}{c|cccccc} n&3&4&5&6&7&8\ \hline h(n)&1&3&4&8&9&13 \end{array} $$

The same computation gives the stronger bounds

$$ h(9)\ge 17,\qquad h(10)\ge 23 . $$

For $n=9$, the optimum is proved by a separate unsatisfiability check at $r=19$, giving

$$ h(9)=18 . $$

For $n=10$, the corresponding upper bound is obtained at $r=24$, giving

$$ h(10)=23 . $$

The construction can be interpreted geometrically. Starting with a proper four-coloring, one may enlarge one color class into a kernel. Every vertex in this enlarged class can simultaneously keep its original color and the additional color, so the size of such a kernel gives a lower bound for $h(n)$. The constructions obtained from the explicit colorings in the preceding exercise give the bounds above. For $n=10$, the resulting coloring exhibits $23$ vertices that simultaneously support two colors, and the SAT upper bound proves that no larger set is possible.

Thus $h(n)$ measures the largest possible overlap between color classes when the exact-one-color clauses are omitted. The first values are

$$ \boxed{ h(3),h(4),h(5),h(6),h(7),h(8),h(9),h(10)

1,3,4,8,9,13,18,23 } $$

with the last two values requiring the extremal SAT verification described above.