Source-linked AI summary
Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable
Matheus Adauto, Celina de Figueiredo, Diana Sasaki, Rafael Schneider
TL;DR
The paper asks when every 4-total coloring of a cubic graph is equitable, challenging Stemock’s conjecture below order 20. Using a decomposition into independent sets and perfect matchings, it proves that order 12 supplies the smallest counterexample and that order 14 is the largest universal order, while counterexamples exist at every even order n ≥16.
Problem
Stemock conjectured that every 4-total coloring of a cubic graph of order less than 20 is equitable.
Method
The paper decomposes each color class into an independent vertex set and a perfect matching of the remaining graph, then uses feasible profiles and splicing constructions.
Results
Every 4-total coloring is equitable at orders 6, 8, 10, and 14, while L12 admits a non-equitable coloring and such colorings exist for every even n ≥16.
Takeaways & Limitations
Order 14 is the largest order for which every 4-total coloring of every cubic graph is equitable.
Takeaways & Limitations
Feasible profiles are necessary conditions only; whether a profile occurs depends on the particular graph.
Abstract
from arXiv · showhide
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\geq16$, 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.
1 Introduction
The paper studies equitable 4-total colorings of cubic graphs, motivated by Stemock’s conjecture that all such colorings below order 20 are equitable. It disproves the conjecture and identifies order 14 as the largest order where the property holds universally.
- A 4-total coloring assigns colors to vertices and edges so adjacent or incident elements receive distinct colors.
- Stemock conjectured that every 4-total coloring of a cubic graph of order less than 20 is equitable.
- The conjecture fails at order 12, where the circular ladder L12 has a non-equitable 4-total coloring.
- Every 4-total coloring of a cubic graph of order 6, 8, 10, or 14 is equitable.
- A splicing operation yields connected cubic graphs with non-equitable 4-total colorings for every even order n ≥16, making 14 the largest universal order.
2 Preliminaries
The preliminaries define equitable total coloring and the graph families used throughout the paper. For cubic graphs, the total number of vertices and edges is determined by the order, and circular ladders provide key examples.
- For a cubic graph of order n, the number of edges is 3n/2 and the total number of elements is 5n/2.
- A 4-total coloring is equitable when any two color classes differ in cardinality by at most one.
- The circular ladder Ln is the prism Cn/2 □ K2, with rungs joining the two cycle copies.
- Among the listed cubic graph families, circular ladders are Type 1 except for L10, while K4, K3,3, and Möbius ladders are Type 2.
3 The structure of 4-total colorings of cubic graphs
The paper reduces 4-total colorings of cubic graphs to independent vertex sets and compatible perfect matchings. This decomposition yields parity, counting, and equitability criteria, while feasible profiles remain only necessary until verified for particular graphs.
- Each color class corresponds to an independent vertex set Si together with a perfect matching Mi of G−Si.
- The four independent sets partition the vertices, and the four matchings partition the edges.
- Every vertex class has even size, and the vertex profile determines the color class configuration.
- Conversely, these independent-set and perfect-matching partitions construct a valid 4-total coloring.
- A 4-total coloring is equitable exactly when the largest and smallest vertex-class sizes differ by at most 2.
- Feasible profiles satisfy even entries, sum to n, 5v1 ≤ 2n, and v2 + 2v1 ≤ n, but feasibility alone does not ensure attainment by a particular graph.
4 Orders 6, 8, 10, and 14
Every 4-total coloring of a cubic graph of order 6, 8, 10, or 14 is equitable. The decomposition lemma reduces the proof to feasible vertex profiles, whose possible forms have maximum-minus-minimum at most 2.
- Orders 6, 8, 10, and 14 all force every 4-total coloring of a cubic graph to be equitable.This extends the known Petersen-graph case.
- The proof uses the decomposition lemma to analyze feasible vertex profiles of 4-total colorings.It suffices to show that each feasible profile satisfies v1 − v4 ≤2.
- At order 14, the only feasible profile is (4, 4, 4, 2), which also has maximum-minus-minimum at most 2.
5 Counterexamples and color class configurations
The paper identifies the smallest counterexample to Stemock’s conjecture at order 12, classifies all color-class configurations at orders 12, 16, and 18, and shows that the listed configurations occur. Circular-ladder constructions further reveal broad families of non-equitable colorings, with order 14 as a genuine exception.
- Order 12: Order 12 is the smallest counterexample: L12 has a non-equitable configuration (8, 8, 8, 6), while every smaller admissible order is equitable.Order 4 is vacuous because K4 has no 4-total coloring; orders 6, 8, and 10 are covered by the preceding theorem.
- Order 12: At order 12, the only configurations are (8, 8, 7, 7) and (8, 8, 8, 6), and both are attained by L12.The first is equitable, whereas the second is the unique non-equitable configuration.
- Order 16: At order 16, the only configurations are (10, 10, 10, 10) and (11, 10, 10, 9), both attained by the connected cubic graph H16.The configuration (11, 10, 10, 9) is the unique non-equitable possibility.
- Order 18: At order 18, the possible configurations are (12, 11, 11, 11), (12, 12, 11, 10), and (12, 12, 12, 9), and all three are attained.The latter two are exactly the non-equitable configurations; L18 attains (12, 12, 12, 9), while H18 attains the other two.
- General constructions: Circular-ladder constructions produce non-equitable colorings precisely at even orders n ≥12 with n ∉{14, 16, 22}; order 14 is a genuine exception.Orders 16 and 22 are exceptions only for that particular construction, since other graphs provide non-equitable colorings there.
6 All larger orders
The paper uses splicing to extend non-equitable 4-total colorings from orders 16, 18, and 20 to every even order at least 16, establishing that order 14 is extremal.
- Splicing construction: A splicing operation merges two totally colored cubic graphs while preserving a 4-total coloring and adding corresponding color-class cardinalities.The construction deletes one edge from each graph, reconnects the exposed endpoints, and permutes one coloring before joining them.
- Splicing construction: The splice lemma chooses a color permutation satisfying the endpoint constraints, with three valid permutations guaranteed by inclusion–exclusion.Among six permutations mapping the selected edge color correctly, exactly 6 − 2 − 2 + 1 = 3 satisfy both endpoint constraints.
- Conclusion: Every even order n ≥16 has a connected cubic graph admitting a non-equitable 4-total coloring, so 14 is the largest order with universal equitability.The induction advances by six from base orders 16, 18, and 20, and every even n ≥16 has one of these residues.
- Inductive construction: Three connected base graphs of orders 16, 18, and 20 admit non-equitable 4-total colorings.The base configurations are (11, 10, 10, 9), (12, 12, 12, 9), and the coloring of R, respectively.
- Inductive construction: Splicing a graph of order n with L6 increases the minimum color class by 3 and every other class by 4, preserving non-equitability.The class-size difference increases from smax − smin to (smax − smin) + 1, which is at least 3.
7 Final remarks
The final remarks contrast the exceptional graph R with the paper’s explicit counterexamples and formulate open classification problems for larger orders.
- Comparison with R: R is Type 1, yet all its 4-total colorings are non-equitable, with χ′′e(R) = 5 > χ′′(R).By contrast, the paper’s explicit counterexamples at orders 12, 16, and 18 also admit equitable 4-total colorings.
- Open question: The paper asks whether every Type 1 cubic graph of order less than 20 admits at least one equitable 4-total coloring.Equivalently, it asks whether R is a minimum-order Type 1 cubic graph with equitable total chromatic number 5.
- Open question: The question is finite after reducing to connected cubic graphs and independently permuting colors across components.This reduction does not remove the general NP-completeness of deciding equitable 4-total colorability.
- Further problem: The paper proposes characterizing, for every even n ≥20, which cubic graphs attain feasible profiles with v1 − v4 ≥4.This extends the complete analyses reported for orders 12, 16, and 18.
A Explicit coloring certificates
The appendix presents certificate-based verification of the listed colorings using independent vertex sets and perfect matchings.
- Certificate structure: Each certificate partitions the vertices into four independent sets and the edges into four perfect matchings of the corresponding vertex-deleted subgraphs.By the decomposition lemma, each such list independently certifies a 4-total coloring without relying on the search computation.
A.1 The graph H16
The H16 appendix section gives explicit vertex-set and matching data for several 4-total colorings, including non-equitable and equitable profiles.
- Non-equitable profiles: H16 has an explicit coloring with profile (6, 4, 4, 2).The certificate specifies each color’s independent vertex set and matching of the remaining graph.
A.2 The graph H18
The section gives explicit independent-set and matching decompositions for color classes in H18, including colorings with profiles (6, 6, 4, 2) and (6, 4, 4, 4).
- Explicit colorings: The coloring with profile (6, 6, 4, 2) specifies independent sets and complementary matchings for all four colors.The color classes use vertex sets of sizes 6, 6, 4, and 2, respectively.