pith. sign in

arxiv: 2605.18783 · v1 · pith:3GYN4GYEnew · submitted 2026-05-06 · 🧮 math.CO

On the Hilton-Zhao vertex-splitting conjecture

Xuli Qi , Yanrui Feng This is my paper

Pith reviewed 2026-05-20 23:31 UTC · model grok-4.3

classification 🧮 math.CO
keywords Hilton-Zhao conjecturevertex splittingedge-chromatic critical graphsregular Class 1 graphschromatic indexgraph coloringconjectures in graph theory
0
0 comments X

The pith

If a connected n-vertex regular Class 1 graph has maximum degree at least (2n-2)/3, then splitting one vertex yields an edge-chromatic critical graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper establishes a partial confirmation of the Hilton-Zhao vertex-splitting conjecture. It proves that when a connected regular Class 1 graph G on n vertices has maximum degree at least (2n-2)/3, the graph G* formed by splitting one vertex into two is edge-chromatic critical. This means every proper subgraph of G* has a strictly smaller chromatic index than G* itself. Sympathetic readers care because criticality results pinpoint the smallest graphs that demand a given number of colors, aiding both theoretical classification and practical problems like edge coloring in networks and timetabling. The result improves on the prior verification which required a larger degree threshold of 3n/4.

Core claim

Assume that G is an n-vertex connected regular Class 1 graph. If Δ(G) ≥ (2n-2)/3, then the graph G* obtained by splitting one vertex into two vertices is edge-chromatic critical.

What carries the argument

The vertex-splitting operation producing G* from G, which carries the argument by creating a new graph whose edge-chromatic criticality must be established.

If this is right

  • The conjecture is verified for all qualifying graphs with Δ at least (2n-2)/3.
  • Such G* graphs are edge-chromatic critical, meaning they are minimal in requiring their chromatic index.
  • This strengthens earlier results by lowering the degree threshold from 3n/4.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The approach might extend to prove the conjecture for smaller degrees down to just above n/3.
  • It connects to broader questions about when graph modifications preserve or increase chromatic index.
  • One could look for small-order examples where the bound is tight to test the result computationally.

Load-bearing premise

The vertex splitting must be performed so that the two new vertices inherit the edges without creating multiple edges and the resulting graph stays simple.

What would settle it

A connected regular Class 1 graph with maximum degree exactly (2n-2)/3 for which some proper subgraph of the split graph G* has the same chromatic index as G* itself.

read the original abstract

Let $G$ be a simple graph with order $n$, maximum degree $\Delta(G)$, and chromatic index $\chi'(G)$, respectively. A graph $G$ is edge-chromatic critical if $\chi'(H)<\chi'(G)$ for every proper subgraph $H$ of $G$. Assume that $G$ is an $n$-vertex connected regular Class $1$ graph, and let $G^*$ be obtained from $G$ by splitting one vertex into two vertices. Hilton and Zhao in 1997 proposed the vertex-splitting conjecture: if $\Delta(G)>\frac{n}{3}$, then $G^*$ is edge-chromatic critical. Recently, Cao, Chen, and Shan (Discrete Math. 2022) verified the conjecture for $\Delta(G)\ge\frac{3n}{4}$. In this paper, we confirm the conjecture for $\Delta(G) \ge\frac{2n-2}{3}$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The paper verifies the Hilton-Zhao vertex-splitting conjecture for n-vertex connected regular Class 1 graphs G with Δ(G) ≥ (2n-2)/3. It proves that the graph G* obtained by splitting one vertex v into two vertices u and w (partitioning the incident edges while preserving simplicity) is edge-chromatic critical, improving on the prior verification for Δ(G) ≥ 3n/4.

Significance. If correct, the result narrows the gap to the full conjecture (which requires only Δ > n/3) by establishing criticality via case analysis on the degree pair (deg(u), deg(w)) with deg(u) + deg(w) = Δ, combined with the Class 1 property of G to produce a Δ-edge-coloring of G* minus a critical edge. The threshold (2n-2)/3 arises naturally from the numerical condition needed to guarantee an overfull subgraph or missing-color argument in the extremal cases. This constitutes a standard but substantive incremental advance in edge-coloring criticality.

minor comments (2)
  1. §3 (or the section containing the main case analysis): explicitly list the subcases for deg(u) = k and deg(w) = Δ - k when k ranges from 1 to floor(Δ/2), including the boundary k = 1, to make the completeness of the argument transparent.
  2. The statement of the main theorem (presumably Theorem 1.1 or 4.1) should include a brief reminder that G remains simple after splitting, as this is invoked in the criticality claim.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive and accurate summary of our manuscript, as well as for recognizing the result as a substantive incremental step toward the full Hilton-Zhao conjecture. We appreciate the recommendation for minor revision.

Circularity Check

0 steps flagged

No significant circularity in derivation chain

full rationale

The paper verifies the Hilton-Zhao conjecture for the improved bound Δ(G) ≥ (2n-2)/3 via case analysis on the degree split of the two new vertices after splitting (with deg(u) + deg(w) = Δ), using the Class 1 property of G to extend or construct a Δ-edge-coloring of G* minus a critical edge. The threshold (2n-2)/3 emerges directly from the numerical condition guaranteeing an overfull subgraph or missing-color argument in the largest case. No self-definitional reductions, fitted inputs renamed as predictions, or load-bearing self-citations appear; the structural definition of vertex splitting is the standard one matching the conjecture statement and is not circular. The proof is self-contained against external graph-theoretic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The claim rests on standard definitions from graph theory (Vizing's theorem, Class 1 graphs, edge-chromatic criticality) and the specific construction of vertex splitting; no free parameters or invented entities are indicated in the abstract.

axioms (2)
  • standard math Vizing's theorem that χ'(G) is either Δ or Δ+1 for simple graphs
    Implicit background for defining Class 1 graphs and criticality in the conjecture statement.
  • domain assumption The vertex-splitting operation produces a simple graph G* whose edges are inherited from the original vertex
    Central to the definition of G* in the conjecture.

pith-pipeline@v0.9.0 · 5684 in / 1505 out tokens · 38606 ms · 2026-05-20T23:31:24.772283+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

10 extracted references · 10 canonical work pages

  1. [1]

    Bonvicini, A

    S. Bonvicini, A. Vietri,A M¨ obius-type gluing technique for obtaining edge-critical graphs, Ars Math. Contemp. 19 (2)(2020) 209–229

    work page 2020

  2. [2]

    Y. Cao, G. Chen, S. Shan,An improvement to the Hilton-Zhao vertex-splitting conjecture, Discrete Math. 345 (2022) 112902

    work page 2022

  3. [3]

    Fiorini, R.J

    S. Fiorini, R.J. Wilson,Edge-Colourings of Graphs, Research Notes in Maths., Pitman, London, 1977

    work page 1977

  4. [4]

    Hilton, C

    A.J.W. Hilton, C. Zhao,Vertex-splitting and chromatic index critical graphs, Discrete Appl. Math. 76 (1997) 205–211

    work page 1997

  5. [5]

    Holyer,The NP-completeness of edge-coloring, SIAM J

    I. Holyer,The NP-completeness of edge-coloring, SIAM J. Comput. 10 (4)(1981) 718–720. 9

    work page 1981

  6. [6]

    Gupta,Studies in the Theory of Graphs, PhD dissertation, Tata Institute of Fun- damental Research, Bombay, 1967

    R.G. Gupta,Studies in the Theory of Graphs, PhD dissertation, Tata Institute of Fun- damental Research, Bombay, 1967

    work page 1967

  7. [7]

    Song,A further extension of Yap’s construction for∆-critical graphs, Discrete Math

    Z. Song,A further extension of Yap’s construction for∆-critical graphs, Discrete Math. 243 (1-3)(2002) 283–290

    work page 2002

  8. [8]

    Stiebitz, D

    M. Stiebitz, D. Scheide, B. Toft, L.M. Favrholdt,Graph edge coloring, Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2012. Vizing’s theorem and Goldberg’s conjecture, With a preface by Stiebitz and Toft

    work page 2012

  9. [9]

    Vietri,An analogy between edge colourings and differentiable manifolds, with a new perspective on 3-critical graphs, Graphs Comb

    A. Vietri,An analogy between edge colourings and differentiable manifolds, with a new perspective on 3-critical graphs, Graphs Comb. 31 (6)(2015) 2425–2435

    work page 2015

  10. [10]

    Vizing,Critical graphs with given chromatic class, Diskretn

    V.G. Vizing,Critical graphs with given chromatic class, Diskretn. Anal. 5 (1965) 9–17. 10

    work page 1965