From semi-total to equitable total colorings, and their induced partitions into perfect and total perfect codes
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
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality