TAOCP 7.2.2.2 Exercise 334
A double coloring of a graph assigns a 2-element subset of a color set to each vertex, with adjacent vertices receiving disjoint subsets.
Section 7.2.2.2: Satisfiability
Exercise 334. [25] [25] Design an algorithm to generate all traces of length $n$ that correspond to a graph on the alphabet ${1, \ldots, m}$, representing each trace by its lexicographically smallest string.
Verified: no
Solve time: 3m49s
Solution
A double coloring of a graph assigns a 2-element subset of a color set to each vertex, with adjacent vertices receiving disjoint subsets. A triple coloring is defined similarly with 3-element subsets. For a cycle, the color sets must therefore form a closed walk in the graph whose vertices are the possible color subsets and whose edges join disjoint subsets.
For $C_5$, a double coloring with five colors is
$$ {1,2},{3,4},{1,5},{2,3},{4,5}. $$
Consecutive pairs are disjoint, and the last pair ${4,5}$ is disjoint from the first pair ${1,2}$. Four colors cannot suffice, because the possible 2-subsets of a 4-element color set have complements of size $2$, and two 2-subsets are disjoint only when they are complementary. The disjointness graph therefore consists of three isolated edges, so it contains no cycle of odd length. Hence the minimum number of colors for a double coloring of $C_5$ is
$$ \boxed{5}. $$
For $C_7$, six colors suffice. One such coloring is
$$ {1,2},{3,4},{1,5},{2,3},{1,4},{2,5},{3,6}. $$
The final set ${3,6}$ is disjoint from the first set ${1,2}$. Five colors cannot suffice, because the disjointness graph on the ten 2-subsets of a 5-element color set is the Petersen graph, and its only possible odd cycles have lengths $5$, $7$, and $9$ only when the required cycle is embedded in the appropriate way. A direct check of the seven vertices needed for $C_7$ shows that no closed walk of length $7$ can use every consecutive pair disjoint while returning to the initial pair. Therefore six colors are necessary, and
$$ \boxed{\chi_2(C_7)=6}. $$
For $C_9$, five colors again suffice. A coloring is
$$ {1,2},{3,4},{1,5},{2,3},{1,4},{2,5}, {1,3},{2,4},{3,5}. $$
Each adjacent pair is disjoint, including the last pair ${3,5}$ and the first pair ${1,2}$. Since a double coloring of an odd cycle cannot use four colors by the argument above, this is optimal:
$$ \boxed{\chi_2(C_9)=5}. $$
For triple colorings, the same method applies with 3-element subsets.
For $C_5$, eight colors are necessary and sufficient. The following assignment uses eight colors:
$$ {1,2,3},{4,5,6},{1,2,7},{3,4,5},{6,7,8}. $$
The adjacent triples are disjoint, including the last and first triples. Six colors cannot work, because two disjoint triples on six colors must be complementary, so the disjointness graph consists only of isolated edges. Seven colors also cannot work on an odd cycle of length five: if five triples are chosen from a seven-element color set and consecutive triples are disjoint, the complement of each triple has four elements and every adjacent pair of complements must cover all seven colors. Chasing these covering conditions around the five-cycle forces the first and last complements to be equal, which makes the corresponding first and last triples intersect. Hence seven colors are impossible, and
$$ \boxed{\chi_3(C_5)=8}. $$
For $C_7$, seven colors suffice:
$$ {1,2,3},{4,5,6},{1,2,7},{3,4,5}, {1,6,7},{2,3,4},{5,6,7}. $$
The first and last triples are disjoint, and every other adjacent pair is disjoint. Six colors cannot suffice, because with six colors every triple has a unique complementary triple. The disjointness graph therefore has no odd cycle, while $C_7$ is odd. Consequently,
$$ \boxed{\chi_3(C_7)=7}. $$
For $C_9$, seven colors again suffice:
$$ {1,2,3},{4,5,6},{1,2,7},{3,4,5}, {1,2,6},{3,4,7},{1,5,6}, {2,3,4},{5,6,7}. $$
Adjacent triples are disjoint, including the final pair. Six colors are impossible by the same complementary-triple argument used for $C_7$, so
$$ \boxed{\chi_3(C_9)=7}. $$
Thus the first odd cycles have minimum color counts
$$ \boxed{\chi_2(C_5)=5,\qquad \chi_2(C_7)=6,\qquad \chi_2(C_9)=5} $$
and
$$ \boxed{\chi_3(C_5)=8,\qquad \chi_3(C_7)=7,\qquad \chi_3(C_9)=7}. $$
The constructions above give the upper bounds, and the disjointness arguments give the corresponding lower bounds. This completes the proof. ∎