Let $G$ be the graph on $n$ vertices $(n \geq 4)$ obtained from $K_n$ by removing $n$ edges
forming an $n$-cycle. Determine the chromatic number of $G$.
For any even $n$ I know that removing the $n$-cycle edges leaves a graph with a $\frac{n}{2}$ clique, so the chromatic number $\chi(G) \geq \frac{n}{2}$. Similarly, for odd $n$, removing the $n$-cycle edges leaves a graph with another (odd) $n$-cycle, so $\chi(G) \geq 3$. I'm not exactly how to proceed from here. Any help would be appreciated!
Best Answer
You should check that for $n>3$, the graph $G$ (commonly denoted as $\overline{C_n}$, the complement of the cycle graph) does not have an independent set of size $3$. Equivalently, for $n>3$, $C_n$ does not contain a triangle.
This means that every color can be used on at most two vertices, and therefore $\chi(\overline{C_n}) \ge \lceil \frac n2 \rceil$. To show that this bound is tight, and conclude that $\chi(\overline{C_n}) = \lceil \frac n2 \rceil$, you should find a coloring that uses this many colors.
Again, it might be easier to think about working with the cycle graph $C_n$, where we want the complement of a proper coloring. That's a vertex coloring where the vertices of each color form a clique. In this case, for each color, there is either only one vertex of that color, or two adjacent vertices.