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

arXiv:2503.20055 · math.CO · Submitted 2025-03-25 · Read on arXiv

math.CO

Submitted: 2025-03-25

Updated: 2026-11-01

Comments: 28 pages, 20 figures

License: http://creativecommons.org/licenses/by-sa/4.0/

The gist: Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number χ''(G) of a connected simple graph G is either Δ(G)+1 or Δ(G)+2…

Terminology

Abstract

Independently posed by Behzad and Vizing, the Total Coloring Conjecture asserts that the total chromatic number χ''(G) of a connected simple graph G is either Δ(G)+1 or Δ(G)+2, where Δ(G) is the largest degree of a vertex of G. Deciding whether a cubic graph G has χ''(G)=Δ(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.

Related papers