I have a question on the Total Coloring Conjecture in graph theory. This conjecture states that

$$\chi^"(G)\leq \Delta +2,$$

where $\Delta$ is the maximum degree of the graph and $\chi^"(G)$ denotes the total coloring (minimum number of colors for coloring graph such that no adjacent edges and no edge and its endpoints are assigned the same color) number.

Question: Has the Total Coloring Conjecture been proved for complete graphs?


1 Answer 1


Yes, of course.

It is known and published for decades that

$n$ odd $\quad\vdash_{n:\omega}\quad$ $\chi''(K^n) = n$,


$n$ even $\quad\vdash_{n:\omega}\quad$ $\rightarrow$ $\chi''(K^n) = n+1$,

and because of $\Delta(K^n)=n-1$, and $n+1 = (n-1)+2$, the conjecture is validated in these instances.

One of the many references is page 160 in

Hian Poh Yap: Total colourings of graphs. Bulletin of the London Mathematical Society 21 (1989) pp. 159-163

I hope you do not mind a small constructive criticism of this question: by and large, such questions seem alright, but there should be more care and research effort visible. I recognize that the following was probably not done due to linguistic friction: you had better asked something like 'Is there any reason why the the Total Coloring Conjecture is trivial for complete graphs', or similar, not 'Has it been proved?'. With the latter kind of question one can find fault in many obvious ways; hopefully we don't have to 'go there'. The former alternative question is not inappropriate (I think), and the answer, roughly, is "No, it's not trivial, but not deep in any way; it can be proved by induction on $n\in\omega$."


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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