The total coloring conjecture (TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree of its vertices. The conjecture is open for many graphs albeit has been proved for several classes of graphs like complete graphs, trees, cycles, multipartite, graphs of maximum degree $3,4,5$, planar graphs of maximum degree greater than or equal to $6$ and some graphs of high degree. My question pertains to the conjecture for Cayley graphs. In order to prove the result for Cayley graphs, for, say, the Cayley graphs of Abelian groups, Can we take the help of structure theorem for finitely generated abelian groups, like, say, since finitely generated abelian groups are products of cyclic groups up to isomorphism, and, suppose, we are able to prove the TCC for Cayley graphs of cyclic groups with respect to a suitable generator set, then, could we extend it to Cayley graphs of all finitely generated abelian groups with generating set as the cartesian product of the individual generating sets? Any thoughts on this approach?

  • $\begingroup$ There is a proof of Total coloring conjecture on arxiv. posted on 2020 but I am not aware of its correctness. $\endgroup$
    – C.F.G
    Commented Oct 30, 2021 at 19:15
  • $\begingroup$ @C.F.G yes, I am aware of it. But, the arguments seem clumsy there $\endgroup$
    – vidyarthi
    Commented Oct 31, 2021 at 19:45

1 Answer 1


Kindly refer recent post in arxiv.org in total colorings and survey. Partial results are available for some classes of Cayley graphs. That is some classes of cayley graphs are type-I and some of them are type-II. For example, some classes of power of cycle graphs and its complements are classified as type-I and type-II. Total coloring conjecture is true for unitary Cayley graph and some circular graphs.


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.