Hilton-Zhao vertex-splitting conjecture for triangle-free graphs
math.CO
Submitted: 2026-10-30
Updated: 2026-10-30
License: http://creativecommons.org/licenses/by/4.0/
The gist: Every graph obtained from a regular Class 1 graph by a vertex-splitting is overfull and hence is of Class 2; the central question is whether the resulting graph is edge-chromatic critical.
Abstract
Every graph obtained from a regular Class 1 graph by a vertex-splitting is overfull and hence is of Class 2; the central question is whether the resulting graph is edge-chromatic critical. We consider a revised version of the Hilton-Zhao vertex-splitting conjecture for triangle-free base graphs, excluding the known cubic exception that arises from the Wagner graph. Let G be a connected n-vertex triangle-free Δ-regular Class 1 graph, and let G* be obtained from G by splitting one vertex into two adjacent vertices. We first show that any non-extreme vertex-splitting produces a Δ-critical graph provided Δ> n-1 over 3. Consequently, for non-extreme vertex-splittings, the revised version of the conjecture is valid across its entire conjectured degree range, and indeed even under a slightly weaker degree condition. We next turn to arbitrary vertex-splittings, extreme ones included. It is shown that G* is Δ-critical provided n at least 10 and Δ> 2n-3 over 5. In addition, for n>24, the non-strict condition Δ at least 2n-3 over 5 is already sufficient. This extends the bipartite range Δ> 2n over 5 to the boundary range that the bipartite argument does not cover. In particular, our arguments give a complete treatment of the case of triangle-free 6-regular base graphs in the conjectured range. The proofs bring together structural properties of full-deficiency pairs, homomorphism theorems for dense triangle-free graphs, and Hamilton decompositions built via graph detachment.
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