From semi-total to equitable total colorings, and their induced partitions into perfect and total perfect codes

Abstract

Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number ${\chi }^{\prime \prime }(G)$ of a connected simple graph $G$ is either $\Delta (G)+1$ or $\Delta (G)+2$, where $\Delta (G)$ is the largest degree of a vertex of $G$. Deciding whether a cubic graph $G$ has ${\chi }^{\prime \prime }(G)=\Delta (G)+1$, even if $G$ is bipartite, is NP-hard. The problem persists even for equitable total colorings. Williams and Holroyd gave a condition for total colorings via the introduction of semi-total colorings. In the present work, focus is set mainly on obtaining, by means of a variation of Kempe's 1879 graph-coloring algorithm, equitable total colorings out of semi-total colorings of: symmetric cubic graphs (3-cube, Petersen, Heawood, Pappus, Desargues, etc., graphs) and cage graphs (Robertson graph, etc.) Moreover, total colorings of the 3-cube and subsequent $4k$-polygon prisms ($k>1$) are shown to exist that have perfect codes as their vertex color classes, as well as semi-total colorings of Möbius ladders that have total-perfect codes as their vertex color classes, only $K_{3,3}$ of which equitable. In addition, a semi-total coloring of the 90-vertex Foster graph is shown to have a vertex color class being a total-perfect code. On the other hand, a semi-total coloring of the 42-vertex $(5,6)$-cage yields a decomposition into 3 copies of the Heawood graph, by the edges of same color endvertices, and 7 6-cycles. Among other cases, non-equitable total colorings of cubic graph expansions are taken to equitable semi-total colorings.

arXiv comment28 pages, 20 figures