Hilton-Zhao vertex-splitting conjecture for triangle-free graphs

arXiv:2610.41984 · math.CO · Submitted 2026-10-30 · Read on arXiv

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