Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here:


Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set

$V=\{a_0, \dots , a_{n-1}, b_0, \dots , b_{n-1}\}$

and with edge set

$E=\{(a_i,b_i), (a_i, a_{i+1\pmod{n}}), (b_i, b_{i+1 \pmod{n}}), (a_i, b_{i+1 \pmod{n}}),(b_i, a_{i+1 \pmod{n}} )\}$

for all $0\le i <n$.

My question is, what is the chromatic number of this graph? For $n$ even, one can easily show that $\chi(Ci_{2n}(1,n-1,n))=4$ by noting that each circulant graph has a four-clique, and then that we may simply alternate colors on the "outer" cycle, and alternate different colors on the "inner" cycle (referring to that link above).

But when $n$ is odd, I am stuck. For $n=3$, we see $Ci_6(1,2,3) \cong K_6$ and so the chromatic number is $6$. For $Ci_{10}(1,4,5)$ I see how to $5$-color the vertices, but I cannot prove that is optimal, nor can I figure out how to generalize this to other odd $n$.

  • $\begingroup$ GraphData[{"Circulant", {24, {1, 11, 12}}}, "ChromaticNumber"] and GraphData[{"Circulant", {10, {1, 4, 5}}}, "ChromaticNumber"] are two cases. Up to n=11, the chromatic number is 5 for the odd cases. We didn't calculate the result for n=15, but that one is worth a look as a possible exception. $\endgroup$ – Ed Pegg Feb 11 '16 at 17:07
  • $\begingroup$ Sorry @EdPegg where is this information located? In a paper? I would love to see it. $\endgroup$ – user3000877 Feb 11 '16 at 18:00
  • $\begingroup$ It's the GraphData function in Mathematica. $\endgroup$ – Ed Pegg Feb 11 '16 at 18:14

Divide the $2n$ vertices of this graph into $n$ pairs $\{a_i, b_i\}$.

In the "musical" version of the picture, we pair each vertex of the outer cycle with the corresponding vertex of the inner cycle. In the "circulant graph" version of the picture, each vertex is paired with the opposite vertex of the cycle.

Either way, the $n$ pairs $\{a_0, b_0\}, \dots, \{a_{n-1}, b_{n-1}\}$ all have the property that:

  • The two paired vertices are connected by an edge.
  • Vertices in two adjacent pairs $\{a_i, b_i\}$ and $\{a_{i+1 \bmod n}, b_{i+1 \bmod n}\}$ are connected in all possible ways: $a_i$ to $a_{i+1 \bmod n}$, $a_i$ to $b_{i+1 \bmod n}$, $b_i$ to $a_{i+1 \bmod n}$, and $b_i$ and $b_{i+1 \bmod n}$.
  • These are all the edges in the graph.

Given any proper coloring of the graph, $a_i$ and $b_i$ must be given different colors, and swapping the colors gives another proper coloring. So we don't have to keep track of which vertex in a pair gets which color. It's enough to say that we assign a set of two colors to each pair $\{a_i, b_i\}$, such that the sets assigned to $\{a_i, b_i\}$ and $\{a_{i+1 \bmod n}, b_{i+1 \bmod n}\}$ are disjoint.

(This is equivalent to a $2$-fold fractional coloring of the cycle $C_n$.)

Now it's easy to prove that $$\chi(\text{Ci}_{2n}(1,n-1,n)) = \begin{cases} 4 & n \text{ is even},\\ 5 & n \text{ is odd and } n \ge 5,\\ 6 & n=3. \end{cases}$$

If we have four colors, then the first pair $\{a_0, b_0\}$ gets some two of them: $C_1$ and $C_2$. The next pair $\{a_1, b_1\}$ must get the other two: $C_3$ and $C_4$. After that, $\{a_2, b_2\}$ must get $C_1$ and $C_2$ again (in some order), and we alternate between the two options. This works out when $n$ is even; when $n$ is odd, the pair $\{a_{n-1}, b_{n-1}\}$ ends up given the colors $C_1$ and $C_2$ at the end, which conflicts with the colors on the first pair. So for odd $n$, the graph is not $4$-colorable.

If we have five colors and $n \ge 5$ is odd, we can break parity by the following trick:

  • Assign colors $C_1$ and $C_2$ to the pair $\{a_0, b_0\}$.
  • Assign colors $C_3$ and $C_4$ to the pair $\{a_1, b_1\}$.
  • Assign colors $C_5$ and $C_1$ to the pair $\{a_2, b_2\}$.
  • Assign colors $C_2$ and $C_3$ to the pair $\{a_3, b_3\}$.
  • Assign colors $C_4$ and $C_5$ to the pair $\{a_4, b_4\}$.
  • From then on, assign the pair $\{a_i, b_i\}$ the colors $C_4$ and $C_5$ when $n$ is even, and the colors $C_1$ and $C_2$ when $n$ is odd.

When we come back around the cycle, the pair $\{a_{n-1}, b_{n-1}\}$ will be given the colors $C_4$ and $C_5$ (because $n-1$ is even), which does not conflict with $\{a_0, b_0\}$.

Finally, when $n=3$, this does not work, but as pointed out in the question, for $n=3$ the graph $\text{Ci}_{6}(1,2,3)$ is the complete graph $K_6$, which has chromatic number $6$.


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.