What is chromatic number of the square of $C_n$? What is chromatic number of the square of $C_n$, for $n \ge 3$ ?
By "the square of $C_n$" I mean graph obtained from $C_n$ (cycle on $n$ vertices) by adding edges between all pairs of vertices with distance 2 on the cycle.
What I figured out:

*

*chromatic number is at least 3, because there are triangles

*if $3|n$ then chromatic number is 3: we color consequitive vertices on the cycle: $0, 1, 2, 0, 1, 2, \ldots $ and so on

*if $4|n$ then chromatic number is at most 4: we color consequitive vertices on the cycle: $0, 1, 2, 3, 0, 1, 2, 3, \ldots $ and so on

Now I'm stuck.
Can anyone help?
 A: Split the problem into a couple of cases. If $3 \mid n$, then as you rightly pointed out, the chromatic number is $3$ since the vertices can be colored according to the sequence $0,1,2,0,1,2,\ldots$ ($3$ colors).
Next, if $n=3k+1$ for positive integer $k$, if we want to color with $3$ colors, we are forced to use the three colors alternatively as in the first case. However, we get caught in the last vertex, proving that the chromatic number cannot be $3$. However, coloring the last vertex with a fourth color proves that the chromatic number is $4$.
Finally, if $n=3k+2$ for positive integer $k$, similar to above, the chromatic number cannot be $3$. It is clear that when $n=5$, the chromatic number must be $5$ since the graph is isomorphic to $K_5$. For $n>5$, we can color the first $8$ vertices according to the pattern $0,1,2,3,0,1,2,3$ and then color the rest of the $3(n-2)$ vertices in the pattern $0,1,2,0,1,2,\ldots$ which proves that the chromatic number is $4$. Thus, for your graph $G$, where $n \geqslant 3$, the chromatic number is as follows:
$$\chi(G)=
\begin{cases}
3 && \text{if $3 \mid n$} \\
5 && \text{if $n=5$} \\
4 && \text{otherwise}
\end{cases}$$
