1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ As part of the definition of a (proper) total coloring, don't you also want to say that no adjacent vertices are assigned the same color? $\endgroup$ – bof May 27 '16 at 9:12
  • $\begingroup$ @bof I wrote that we assume total coloring is always proper :) $\endgroup$ – Arman Malekzadeh May 27 '16 at 12:58
  • $\begingroup$ No, you wrote that "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." $\endgroup$ – bof May 27 '16 at 18:24
  • $\begingroup$ @bof i made the edit :) are u satisfied now friend ? :) also ... that definition was from Wikipedia ... i just wanted to write a good definition and that's why some people say that we cannot trust Wikipedia always :) anyway ... thank you :) $\endgroup$ – Arman Malekzadeh May 27 '16 at 19:45
  • $\begingroup$ You used an unattributed quotation from Wikipedia?? How deplorable. $\endgroup$ – bof May 27 '16 at 20:04
3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ According to the OP's definition of total coloring, $\chi''(C_{2n})=3;$ we can color the edges alternately red and blue, and color all the vertices green. $\endgroup$ – bof May 27 '16 at 9:16
  • 1
    $\begingroup$ Of course, according to another definition of total coloring which I've seen elsewhere, adjacent vertices must also get different colors, and so $\chi''(C_n)=\chi(C_{2n}^2).$ $\endgroup$ – bof May 27 '16 at 9:19
  • $\begingroup$ @bof: I have to admit that I overlooked the nonstandard definition the OP gave, but even if I had noticed it, I would have assumed that the OP simply made an error when writing down the definition of total coloring: nobody defines total coloring the way he did. $\endgroup$ – Leen Droogendijk May 27 '16 at 12:09
  • 1
    $\begingroup$ @LeenDroogendijk that definition wasn't from me dude :) that was from Wikipedia en.wikipedia.org/wiki/Total_coloring ... but what i meant was clear :) and u see that even Wikipedia defines total coloring in that way :)) so it's not true that "nobody defines total coloring the way Wikipedia did" :)) thank you for the answer :) $\endgroup$ – Arman Malekzadeh May 27 '16 at 19:58
  • $\begingroup$ You win :) That Wikipedia definition is. at the very least, ambiguous, since it can easily be interpreted incorrectly. $\endgroup$ – Leen Droogendijk May 28 '16 at 7:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.