According to Wikipedia, In graph theory, total coloring is a type of graph coloring on the vertices and edges of a graph. When used without any qualification, a total coloring is always assumed to be proper in the sense that no adjacent edges and no edge and its endvertices are assigned the same color.
Note : Just to make the definition more clear …
In total coloring, No adjacent vertices have the same color.
The total chromatic number $\chi''(G)$ of a graph $G$ is the least number of colors needed in any total coloring of $G$.
Question : Prove that if $n$ is a multiple of 3, $\space\chi''(C_n)=3$ and otherwise, $\space \chi''(C_n)=4$ .
Note : I have no idea how to prove this. But i know that $\chi''(G) \ge \Delta(G)+1$.
Thanks in advance.
Best Answer
First we establish the upper bound by exhibiting a 3-(total-)coloring for $C_n$ when $3\mid n$ and a 4-coloring for all $n$.
When $n\mid 3$ color the vertices red, green, blue cyclically. Color the edge between two vertices with the only color that is not used on its endpoints. This is a proper total coloring with 3 colors (verify!).
When $n$ is even we alternately color the vertices with red and green, and we alternately color the edges with blue and yellow. This is a proper total coloring with 4 colors (verify!).
When $n$ is odd we go clockwise around the cycle and start coloring vertices alternately with red and green. The last vertex would cause two adjacent red vertices, so we color it blue instead. Now we walk around the cycle again and when we go from a red to a green vertex we color the edge blue, when we go from a green to a red vertex we color the edge blue, when we go from a green to a blue vertex (only once) we color the edge red and when we go from a blue to a red vertex (only once) we color the edge green. This is a proper total coloring with 4 colors (verify!).
Since $\chi''(G)\geq\Delta(G)+1=3$ we are already done with the case $3\mid n$.
For the last part we need to show that no proper 3-total-coloring is possible, unless $n$ is a multiple of 3.
Let $v_1,\ldots,v_n$ be the vertices of $C_n$ and assume we have a proper 3-coloring. $v_1$, $v_2$ and edge $v_1v_2$ must have all different colors, say red, green, blue respectively. Now edge $v_2v_3$ cannot be green or blue, so it must be red. Vertex $v_3$ cannot be green or red, so it must be blue. Continuing this process you see that the entire coloring is forced and that we end up with a cyclic coloring of the vertices with period three just as we used above (verify!). Clearly this is only possible when $n$ is a multiple of 3.