Chromatic number of complement of cycle graph

Question

What is the chromatic number of the complement of the cycle graph, $\chi(\overline{C_n})$?

Answer 1

If $n=3$, then $\chi(\overline{C_n}) = 1$.

Next, suppose $n > 3$.

Since each vertex of $\overline{C_n}$ has degree $n-3$, a vertex can only share a color with the two non-adjacent vertices, but not both, so there can be at most $2$ vertices of each color, hence $\chi(\overline{C_n}) \ge \left\lceil {\large{\frac{n}{2}}} \right\rceil $.

But a coloring with $\left\lceil{\large{\frac{n}{2}}}\right\rceil$ colors is achievable as follows . . .

• Regard the vertices of $C_n$ as the vertices of a regular $n$-gon in the plane.$\\[4pt]$
• Starting with an arbitrary vertex and proceeding counterclockwise, color each $2$ consecutive vertices (or the last remaining vertex if $n$ is odd) the same color, but different from any previously used color.

It follows that $\chi(\overline{C_n}) = \left\lceil {\large{\frac{n}{2}}} \right\rceil $.

Answer 2

No color can appear in more than $2$ vertices. The only way to get even $2$ vertices to have the same color is if they're neighbors in the cycle, but then together they prevent every other vertex from getting the color.

On the other hand, it's easy to color the graph with $\lceil n/2\rceil$ colors -- just assign each color to a pair of originally-neighbor vertices.

Exception: This argument breaks down when $n\le 3$, in which case the graph has no edges and its chromatic number is $1$.