Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
Abstract
A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder L12 admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph G, each color class consists of an independent set S together with a perfect matching of G−S. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even n≥16, some connected cubic graph of order n admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.
Related
- On a finite group in which every maximal subgroup of order divisible by p containing the normalizer of some Sylow subgroup is nilpotent
- On a finite group in which every non-nilpotent maximal invariant subgroup of order divisible by p is normal
- Edge‐Coloring a Graph G so That Every Copy of a Graph H Has an Odd Color Class
- A square-root law for equitable coloring
- Quantum n-coloring is undecidable for every n ≥ 3
BibTeX
@misc{adauto2026order,
title = {{Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable}},
author = {Matheus Adauto and Celina de Figueiredo and Diana Sasaki and Rafael Schneider},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05259},
eprint = {2609.05259},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05259},
}
RIS
TY - UNPB
TI - Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
AU - Matheus Adauto
AU - Celina de Figueiredo
AU - Diana Sasaki
AU - Rafael Schneider
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05259
UR - https://arxiv.org/abs/2609.05259
AB - A total coloring of a graph is an assignment of colors to its vertices and edges so that adjacent or incident elements receive distinct colors, and it is equitable when the cardinalities of any two color classes differ by at most one. Stemock conjectured that every $4$-total coloring of a cubic graph of order less than $20$ is equitable. In this paper, we disprove this conjecture: the circular ladder L_12 admits a non-equitable $4$-total coloring and, moreover, no smaller counterexample exists: order $4$ is vacuous, and every $4$-total coloring of a cubic graph of order $6$, $8$, or $10$ is equitable. We also prove that the same property holds at order $14$. Our proofs rely on a decomposition lemma, which states that, in any $4$-total coloring of a cubic graph G, each color class consists of an independent set S together with a perfect matching of G−S. We use the lemma to determine all possible color class configurations for orders $12$, $16$, and $18$, and we show that every listed configuration is attained. Finally, we provide a splicing construction showing that, for every even n≥16, some connected cubic graph of order n admits a non-equitable $4$-total coloring. We may conclude that $14$ is the largest order for which every $4$-total coloring of every cubic graph is equitable.
ER -