I am trying to solve the following question but I am confused where $\chi^{'}(G_n)$ comes from and how to go about solving for each $n$. I know that the chromatic number of a $C_n$ where $n > 1$ is 3 for odd $n$; 2 for even $n$. Or does my following attempt to part (a) work and can I apply a similar approach to part (b)? Thank you for your help.
Let $G_n$ be the graph with vertices $x_1, \ldots, x_n$ and edges
$E = \{x_ix_{(i+1) \bmod n}, x_ix_{(i+2) \bmod n} : 1 \le i \le n\}$
(i. e. a cycle $C_n$ with edges added between all pairs of vertices two apart.)
(a) For each $n$, compute $\chi(G_n)$.
(b) For each $n$, compute $\chi^{'}(G_n)$
=========== Here is my answer for (a) :
We will proceed by induction. Consider the $C_n$ defined above. We claim that $\chi(G_n) = n$ for all $n$. \
The case where $n = 3$ is trivial. So for our base case, we will consider $C_n$ such that $n = 4$, which gives us a $K_4$. We know that $\chi(K_n) = n$ for any \textit{n} (as we covered in lecture that if $G$ contains an $m$-clique then $\chi(G) \ge m$). See the graph below where $\chi(G_n) = n$:
// here I draw a $K_4$ each n in a different color.
For our inductive step, let $G = C_n{+1}$. We see that since $C_n$ defined as above constructs a $n$-clique for any \textit{n}, we always get $\chi(G_n) = n$. See the graph where $\chi(G_n) = C_5$.
// here I draw a $C_5$ every node having a different color.
We see that this holds for $\textit{n = 5}$ as well as every $\textit{n}$ where $n > 5$.
For the part (a):
If $n \leq 5$, then $\chi(G_n) = n$. For $n \geq 6$, we have that if $n \equiv 0 \pmod 3$, then $\chi(G_n) = 3$ (it's just color $1, 2, 3$ alternately). If $n \equiv 1, 2 \pmod 3$, it's easy to prove that $3$ colors are not sufficient. Probably there is an explicit construction, but you can use Brook's theorem to prove that $\chi(G_n) = 4$.