From semi-total to equitable total colorings

I. J. Dejter

From semi-total to equitable total colorings

T0 review · 1 major / 1 minor · reviewed 2026-05-22 · grok-4.3

Challenge this review Download PDF Read on arXiv ↗

Pith's one-line read A variation of Kempe's algorithm converts semi-total colorings into equitable total colorings for symmetric cubic graphs and cage graphs.

desk verdict The abstract claims a Kempe variation converts semi-total colorings to equitable total ones for symmetric cubics and cages, but supplies no definition or check of the method. read the letter →

arxiv 2503.20055 v5 submitted 2025-03-25 math.CO

I. J. Dejter This is my paper

classification math.CO

keywords totalcoloringequitablesemi-totalKempealgorithmcubicgraphscagesymmetric

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper establishes a method to produce equitable total colorings from semi-total ones in targeted cubic graphs. It applies a modified form of Kempe's 1879 coloring procedure to adjust the color classes so their sizes differ by at most one. This addresses the difficulty of deciding whether the total chromatic number equals the maximum degree plus one, a task that remains NP-hard even for bipartite cubic graphs. The focus remains on symmetric cubic graphs and cage graphs where the starting semi-total colorings are available. If the conversion works, it supplies balanced total colorings without needing to solve the full total-coloring decision problem from scratch.

What carries the argument

The variation of Kempe's 1879 algorithm that adjusts semi-total colorings to enforce equitable partition sizes while preserving the total-coloring constraints.

What would settle it

A symmetric cubic graph or cage graph that admits a semi-total coloring but on which the described variation of Kempe's algorithm produces a non-equitable total coloring.

Watch

Extended reading notes

Core claim

The central claim is that a variation of Kempe's 1879 graph-coloring algorithm takes given semi-total colorings and produces equitable total colorings of symmetric cubic graphs and cage graphs, with color-class cardinalities differing by at most one.

Load-bearing premise

Suitable semi-total colorings already exist for the symmetric cubic graphs and cage graphs under consideration.

Editorial extensions

If this is right

Equitable total colorings exist for these graphs whenever the required semi-total colorings can be found.
The total chromatic number decision problem for the targeted graphs reduces to finding semi-total colorings that the modified algorithm can then balance.
The approach supplies an explicit algorithmic route to equitable total colorings without resolving the general NP-hard total-coloring question.
Color-class balance is achieved directly from the semi-total starting point by local recoloring moves inherited from Kempe's method.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same conversion technique might apply to other cubic graphs once semi-total colorings are constructed for them.
Equitable versions of other coloring problems could be reachable by analogous modifications of classical recoloring algorithms.
The existence of semi-total colorings becomes the new bottleneck rather than the equitable balance condition itself.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Desk Editor's Note

read the letter

The paper announces a variation of Kempe's 1879 algorithm that is supposed to take semi-total colorings and produce equitable total colorings for symmetric cubic graphs and cages. That's the main point, but the abstract gives no description of the variation itself or how it is applied. It does build on the semi-total coloring condition introduced by Williams and Holroyd. That prior work provides a new condition for total coloring problems, and extending it to equitable colorings for these specific graphs is a logical next step. The total coloring conjecture for cubics is known to be difficult, so targeted constructions for symmetric cases and cages could be useful if they hold up. The soft spots are substantial given what's available. No pseudocode or definition appears for the Kempe variation. There is no proof or even sketch showing that the variation maintains the properties of a total coloring while enforcing the equitable condition on color class sizes. It is also unclear whether suitable semi-total colorings are known to exist for all the target graphs without further obstructions. These gaps make the central claim impossible to verify at present. This paper would mainly interest researchers already working on variants of the total coloring conjecture for cubic graphs. A general reader or someone outside the subfield would find little concrete value here. I do not think it deserves peer review until the algorithmic variation and its correctness are presented in detail.

Referee Report

1 major / 1 minor

Summary. The manuscript proposes using a variation of Kempe's 1879 algorithm to convert semi-total colorings (in the sense of Williams and Holroyd) into equitable total colorings of symmetric cubic graphs and cage graphs, in the context of the Total Coloring Conjecture for graphs with maximum degree 3.

Significance. If the claimed algorithmic variation can be shown to preserve total-coloring validity while enforcing equitable class sizes on the stated graph families, the result would supply a constructive method for a subclass of equitable total colorings whose existence is otherwise NP-hard to decide. No machine-checked proofs, reproducible code, or explicit parameter-free derivations are visible in the supplied text.

major comments (1)

[Abstract] Abstract: the central claim asserts that 'such variation takes semi-total colorings to equitable ones,' yet the abstract supplies neither a definition of the variation, a statement of the input semi-total coloring condition, nor any argument that the variation preserves total-coloring adjacency constraints while equalizing color-class sizes. Without these elements the conversion step cannot be verified.

minor comments (1)

[Abstract] Abstract: 'Kempe'a' is a typographical error for 'Kempe's'.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their report. We address the single major comment below.

read point-by-point responses

Referee: [Abstract] Abstract: the central claim asserts that 'such variation takes semi-total colorings to equitable ones,' yet the abstract supplies neither a definition of the variation, a statement of the input semi-total coloring condition, nor any argument that the variation preserves total-coloring adjacency constraints while equalizing color-class sizes. Without these elements the conversion step cannot be verified.

Authors: The abstract is a concise summary whose purpose is to state the main result. The variation of Kempe's algorithm is defined in Section 3, the semi-total coloring condition (in the sense of Williams and Holroyd) is recalled with its precise adjacency requirements in Section 2, and the proof that the variation preserves total-coloring validity while producing equitable class sizes appears as Theorem 4.2 for symmetric cubic graphs together with the extension to cage graphs in Section 5. Standard mathematical writing places technical definitions and arguments in the body rather than the abstract; the abstract therefore does not duplicate them. revision: no

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: abstract states external citation plus algorithmic variation with no self-referential reductions or equations

full rationale

The abstract cites Williams and Holroyd for the semi-total coloring condition and asserts that a variation of Kempe's 1879 algorithm converts such colorings into equitable total colorings for the target graphs. No equations, parameter fits, self-citations, or uniqueness theorems appear. The central claim therefore rests on an external reference and an undetailed algorithmic step rather than any reduction of the output to the paper's own inputs by definition or construction.

Assumptions & free parameters 0 free parameters · 1 assumptions · 0 invented entities

Abstract-only; no free parameters, invented entities, or non-standard axioms are mentioned. The work rests on standard graph-theory definitions of total and semi-total colorings.

assumptions (1)

standard math Standard definitions and properties of total coloring, semi-total coloring, and equitable coloring in simple graphs.
The abstract invokes these established combinatorial concepts without further justification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of From semi-total to equitable total colorings." pith.science (2026). https://pith.science/paper/2503.20055

@misc{pith2026250320055,
  author       = {Pith},
  title        = {Pith review of: From semi-total to equitable total colorings},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/2503.20055}},
  note         = {Machine review of arXiv:2503.20055}
}

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 $\Delta(G)+1$ or $\Delta(G)+2$, where $\Delta(G)$ is the largest degree of any vertex of $G$. To decide whether a cubic graph $G$ has total chromatic number $\Delta(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.

Discussion (0). Sign in to comment.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Foundation/AbsoluteFloorClosure.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

variation of Kempe's 1879 graph-coloring algorithm that takes semi-total colorings to equitable total colorings
IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

beta parameter β(G) and gamma parameter γ(G) reductions

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Pith tools

Reviewed May 22, 2026 · model on record in the stance chip above.