From semi-total to equitable total colorings

Abstract

Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number of a simple connected graph $G$ is either $\hat{I}”(G)+1$ or $\hat{I}”(G)+2$, where $\hat{I}”(G)$ is the largest degree of any vertex of $G$. To decide whether a cubic graph $G$ has total chromatic number $\hat{I}”(G)+1$, even for bipartite cubic graphs, is NP-hard. The resulting problems and research persist even for total colorings that are equitable, namely with the cardinalities of the color classes differing at most by 1. Williams and Holroyd gave a new condition to solve total coloring problems via the introduction of semi-total colorings. We focus on how to obtain equitable total colorings of symmetric cubic graphs and cage graphs by means of a variation of Kempe'a 1879 graph-coloring algorithm. Such variation takes semi-total colorings to equitable ones.

26 pages, 20 figures