Hilton-Zhao vertex-splitting conjecture for triangle-free graphs
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)/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 ≥ 10 and Δ>(2n−3)/5. In addition, for n>24, the non-strict condition Δ≥ (2n−3)/5 is already sufficient. This extends the bipartite range Δ>2n/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
BibTeX
@misc{qi2026hiltonzhao,
title = {{Hilton-Zhao vertex-splitting conjecture for triangle-free graphs}},
author = {Xuli Qi and Xin Tian and Gregory Gutin},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.41984},
eprint = {2610.41984},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.41984},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Hilton-Zhao vertex-splitting conjecture for triangle-free graphs
AU - Xuli Qi
AU - Xin Tian
AU - Gregory Gutin
PY - 2026
DA - 2026/10/30
PB - arXiv
DO - 10.48550/arxiv.2610.41984
UR - https://arxiv.org/abs/2610.41984
AB - 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)/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 ≥ 10 and Δ>(2n−3)/5. In addition, for n>24, the non-strict condition Δ≥ (2n−3)/5 is already sufficient. This extends the bipartite range Δ>2n/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.
ER -