pith. sign in

arxiv: 2607.02270 · v1 · pith:KOGVDNNLnew · submitted 2026-07-02 · 🧮 math.CO

Towards the Overfull Conjecture II

Guantao Chen , Jessica McDonald , Songling Shan This is my paper

Pith reviewed 2026-07-03 10:28 UTC · model grok-4.3

classification 🧮 math.CO
keywords overfull conjectureedge coloringchromatic indexclass 2 graphsrobust expandersmaximum degreeVizing theorem
0
0 comments X

The pith

The Overfull Conjecture holds for robust expanders meeting density constraints and therefore for all large graphs with maximum degree at least (1+ε) times half their order.

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

The paper establishes that the Overfull Conjecture is true for graphs that are robust expanders and satisfy given density constraints. If true, this means any class 2 graph in this family must contain a subgraph that is overfull with respect to the maximum degree, forcing the chromatic index to be Δ+1. The authors derive from this that the conjecture applies to every sufficiently large graph whose maximum degree exceeds half the vertex count by any fixed positive proportion. This step brings the conjecture closer to covering all graphs where the degree condition Δ > n/3 holds, potentially enabling efficient coloring decisions in those cases.

Core claim

We confirm the Overfull Conjecture for robust expanders satisfying certain density constraints. As a consequence, for every 0<ε<1, the conjecture holds for all sufficiently large graphs G with maximum degree at least (1+ε)|V(G)|/2.

What carries the argument

Robust expanders satisfying the stated density constraints, which are used to guarantee a Δ-overfull subgraph whenever the graph is class 2.

If this is right

  • The Overfull Conjecture holds for all sufficiently large graphs with maximum degree at least (1+ε)|V(G)|/2 for any ε>0.
  • A polynomial-time algorithm exists for determining the chromatic index of all such graphs.
  • The Just-overfull Conjecture and the Vertex-splitting Conjecture hold for all such graphs.

Where Pith is reading between the lines

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

  • Expansion properties may prove useful for verifying the conjecture at lower degree thresholds than currently known.
  • The approach links mixing properties of expanders directly to the existence of overfull subgraphs in edge-coloring problems.
  • Similar density-based arguments could be tested on other families of graphs that are not necessarily expanders.

Load-bearing premise

The graphs under consideration must be robust expanders that satisfy the paper's density constraints.

What would settle it

A large robust expander satisfying the density constraints that is class 2 but contains no Δ-overfull subgraph would disprove the claim.

Figures

Figures reproduced from arXiv: 2607.02270 by Guantao Chen, Jessica McDonald, Songling Shan.

Figure 1
Figure 1. Figure 1: An illustration of Case (S2.1) when |W ∗ i−1 | is odd. The blue solid edges are the edges of M1 i−1 used in Mi , the red solid edge is the additional edge from M2 i−1 , and the orange dashed edges form the matching Ni . Here a1, a3 ∈ V (G′ 0 ), while a2, b3 ∈ U0. Thus Ni projects a2, b3 to c1, c2 ∈ V (G′ 0 ), and {xi,1, yi,1, xi,2, yi,2} = {a1, c1, a3, c2}. Case S2.2. Suppose that |W∗ i−1 | = 1 and [PITH_… view at source ↗
Figure 2
Figure 2. Figure 2: An illustration of Case (S2.2.1). Here W ∗ i−1 = {w}. We choose Mi = M1 i−1 so that Mi does not cover the vertex x ∗ ; the dashed red edge indicates the unused edge of M2 i−1 covering x ∗ . The unique vertex in V (Mi) \ W∗ i−1 is x ∗ i,1 = a, and we set y ∗ i,1 = x ∗ . In this example, a ∈ U0, so the matching Ni projects a to b = ρi(a) ∈ V (G′ 0 ), while x ∗ ∈ V (G′ 0 ) already represents itself. Thus xi,1… view at source ↗
Figure 3
Figure 3. Figure 3: An illustration of Case (S2.5). For each vertex z ∈ Bi , we choose two distinct neighbors zi,1, zi,2 in V (G′ 0 ) \ (Zi ∪V (Ni)). The orange dashed edges are added to N∗ i , while the green dotted edge ez = zi,1zi,2 is the auxiliary edge used in the projected cycle on V (G′ 0 ). When the cycle is projected back, ez is replaced by the two-edge path zi,1zzi,2. The figure shows two such vertices, z and z ′ , … view at source ↗
Figure 4
Figure 4. Figure 4: An illustration of the projection structure. The left panel represents [PITH_FULL_IMAGE:figures/full_fig_p024_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Illustration of the construction of S i j (v) and T i j (v), assuming v ∈ A. Dashed cross-part edges are uncolored edges of H, the bundles of solid edges represent good edges of color i, and the curved arrows indicate the robust-neighborhood step with the forbidden set Wi removed. In particular, |S i 0 (v)| > 1 6 αn > 4τ |A|. Since the partition is balanced, write m = |A| = |B|. Grow the sets S i j (v) usi… view at source ↗
Figure 6
Figure 6. Figure 6: Illustration of the two alternating-path constructions for [PITH_FULL_IMAGE:figures/full_fig_p063_6.png] view at source ↗
read the original abstract

Let $G$ be a simple graph with maximum degree $\Delta(G)$. A subgraph $H\subseteq G$ is $\Delta(G)$-overfull if $|E(H)|>\Delta(G)\left\lfloor |V(H)|/2\right\rfloor$. In any edge coloring of $G$, each color class restricted to $H$ is a matching of size at most $\left\lfloor |V(H)|/2\right\rfloor$. Thus, if $G$ contains a $\Delta(G)$-overfull subgraph, then $G$ cannot be edge-colored with only $\Delta(G)$ colors. By Vizing's Theorem, $\chi'(G)\le \Delta(G)+1$, and hence $G$ is class $2$. In 1986, Chetwynd and Hilton conjectured that whenever $\Delta(G)>|V(G)|/3$, the converse also holds: every class $2$ graph $G$ contains a $\Delta(G)$-overfull subgraph. This statement, commonly known as the Overfull Conjecture, is one of the most influential conjectures in graph edge coloring. It would imply a polynomial-time algorithm for determining the chromatic index of graphs $G$ with $\Delta(G)>|V(G)|/3$, and would also imply several other longstanding conjectures in the area, including the Just-overfull Conjecture and the Vertex-splitting Conjecture. In previous work, the third author verified the conjecture for large graphs $G$ with maximum degree at least $13|V(G)|/14$. In this paper, we confirm the conjecture for robust expanders satisfying certain density constraints. As a consequence, for every $0<\varepsilon<1$, the conjecture holds for all sufficiently large graphs $G$ with maximum degree at least $(1+\varepsilon)|V(G)|/2$.

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 Overfull Conjecture (that every class-2 graph G with Δ(G) > |V(G)|/3 contains a Δ(G)-overfull subgraph) for the subclass of robust expanders satisfying certain density constraints. As a consequence, for every ε > 0 the conjecture holds for all sufficiently large graphs G with Δ(G) ≥ (1 + ε)|V(G)|/2. This extends the authors' prior verification for Δ(G) ≥ 13|V(G)|/14 and is obtained by showing that the target high-degree graphs fall into the handled expander class for large n.

Significance. If the verification holds, the result is a meaningful advance on the Overfull Conjecture: it lowers the degree threshold from 13n/14 to roughly n/2 (for large n) and thereby brings the conjecture within reach of a larger family of graphs. The consequence also yields a polynomial-time algorithm for χ'(G) in this regime and supports several related conjectures (Just-overfull, Vertex-splitting). The approach of isolating a robust-expander subclass with explicit density conditions is a standard and potentially reusable technique in the area.

minor comments (2)
  1. The abstract states the density constraints only qualitatively; a precise statement of the required expansion and density parameters (e.g., the constants appearing in the definition of “robust expander”) should be given already in the abstract or the first paragraph of the introduction.
  2. The transition from the expander case to the high-degree consequence (final sentence of the abstract) relies on showing that every sufficiently large graph with Δ ≥ (1+ε)n/2 is a robust expander meeting the density conditions; a brief indication of the quantitative n0(ε) or the expansion parameters used would help the reader assess the scope.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report, the assessment of significance, and the recommendation of minor revision. The referee correctly notes that the result extends our prior verification from Δ(G) ≥ 13|V(G)|/14 to the regime Δ(G) ≥ (1+ε)|V(G)|/2 for large n via the robust-expander subclass. No major comments are listed in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper verifies the Overfull Conjecture directly on the subclass of robust expanders meeting explicit density constraints, then derives the high-degree consequence by showing such graphs fall into the handled class for large n. The provided abstract and context contain no fitted parameters renamed as predictions, no self-definitional reductions, no load-bearing self-citation chains, and no imported uniqueness theorems or ansatzes. The cited prior work by the third author addresses a different degree bound and is not required for the new verification. The derivation is therefore self-contained as a standard mathematical proof on a restricted class.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The claim rests on the standard definition of overfull subgraphs, Vizing's theorem, and the background theory of robust expanders; no free parameters or invented entities appear in the abstract.

axioms (1)
  • standard math Vizing's theorem: χ'(G) ≤ Δ(G) + 1
    Invoked to conclude that presence of a Δ-overfull subgraph implies the graph is class 2.

pith-pipeline@v0.9.1-grok · 5861 in / 1184 out tokens · 36246 ms · 2026-07-03T10:28:09.934638+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

31 extracted references · 1 canonical work pages

  1. [1]

    Alon and J

    N. Alon and J. H. Spencer.The Probabilistic Method. Wiley-Interscience Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, third edition, 2008

    2008

  2. [2]

    J. A. Bondy and U. S. R. Murty.Graph theory, volume 244 ofGraduate Texts in Mathematics. Springer, New York, 2008

    2008

  3. [3]

    Cao and G

    Y. Cao and G. Chen. On the average degree of edge chromatic critical graphs II.J. Combin. Theory Ser. B, 145:470–486, 2020

    2020

  4. [4]

    Chetwynd and A

    A. Chetwynd and A. Hilton. The edge-chromatic class of graphs with maximum degree at least|V| −3.Ann. Discrete Math., 41:91–110, 1988

    1988

  5. [5]

    A. G. Chetwynd and A. J. W. Hilton. Regular graphs of high degree are 1-factorizable.Proc. London Math. Soc. (3), 50(2):193–206, 1985

    1985

  6. [6]

    A. G. Chetwynd and A. J. W. Hilton. Star multigraphs with three vertices of maximum degree. Math. Proc. Cambridge Philos. Soc., 100(2):303–317, 1986

    1986

  7. [7]

    Csaba, D

    B. Csaba, D. K¨ uhn, A. Lo, D. Osthus, and A. Treglown. Proof of the 1-factorization and Hamilton decomposition conjectures.Mem. Amer. Math. Soc., 244(1154):v+164, 2016

    2016

  8. [8]

    Fiorini and R

    S. Fiorini and R. J. Wilson. Edge-colourings of graphs, Research notes in Maths.Pitman, London, 1977

    1977

  9. [9]

    Gao and S

    Y. Gao and S. Shan. Linear arboricity of robust expanders.arXiv:2405.18494, 2024

    work page arXiv 2024

  10. [10]

    Gir˜ ao, B

    A. Gir˜ ao, B. Granet, D. K¨ uhn, A. Lo, and D. Osthus. Path decompositions of tournaments. Proc. Lond. Math. Soc. (3), 126(2):429–517, 2023

    2023

  11. [11]

    Gr¨ unewald and E

    S. Gr¨ unewald and E. Steffen. Independent sets and 2-factors in edge-chromatic-critical graphs. J. Graph Theory, 45(2):113–118, 2004

    2004

  12. [12]

    R. P. Gupta.Studies in the Theory of Graphs. PhD thesis, Tata Institute of Fundamental Research, Bombay, 1967

    1967

  13. [13]

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

    1997

  14. [14]

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

    1981

  15. [15]

    D. K¨ onig. ¨Uber Graphen und ihre Anwendung auf Determinantentheorie und Mengenlehre. Math. Ann., 77(4):453–465, 1916

    1916

  16. [16]

    K¨ uhn, A

    D. K¨ uhn, A. Lo, D. Osthus, and K. Staden. The robust component structure of dense regular graphs and applications.Proc. Lond. Math. Soc. (3), 110(1):19–56, 2015

    2015

  17. [17]

    K¨ uhn and D

    D. K¨ uhn and D. Osthus. Hamilton decompositions of regular expanders: applications.J. Combin. Theory Ser. B, 104:1–27, 2014

    2014

  18. [18]

    K¨ uhn, D

    D. K¨ uhn, D. Osthus, and A. Treglown. Hamiltonian degree sequences in digraphs.J. Combin. Theory Ser. B, 100(4):367–380, 2010

    2010

  19. [19]

    C. J. H. McDiarmid. The solution of a timetabling problem.J. Inst. Math. Appl., 9:23–34, 1972

    1972

  20. [20]

    T. Niessen. How to find overfull subgraphs in graphs with large maximum degree. II.Electron. J. Combin., 8(1):Research Paper 7, 11, 2001

    2001

  21. [21]

    Osthus and K

    D. Osthus and K. Staden. Approximate Hamilton decompositions of robustly expanding reg- ular digraphs.SIAM J. Discrete Math., 27(3):1372–1409, 2013

    2013

  22. [22]

    Plantholt

    M. Plantholt. The chromatic index of graphs with large even ordernand minimum degree at least 2n/3.Discrete Math., 345(7):Paper No. 112880, 6, 2022

    2022

  23. [23]

    M. J. Plantholt and S. Shan. Edge coloring graphs with large minimum degree.J. Graph Theory, 102(4):611–632, 2023

    2023

  24. [24]

    P. D. Seymour. On multicolourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. London Math. Soc. (3), 38(3):423–460, 1979

    1979

  25. [25]

    S. Shan. The overfull conjecture on graphs of odd order and large minimum degree.J. Graph Theory, 106(2):322–351, 2024

    2024

  26. [26]

    S. Shan. Towards the Overfull Conjecture.J. Graph Theory, 112(4):370–408, 2026

    2026

  27. [27]

    Stiebitz, D

    M. Stiebitz, D. Scheide, B. Toft, and L. M. Favrholdt.Graph Edge Coloring: Vizing’s Theorem and Goldberg’s Conjecture. Wiley Series in Discrete Mathematics and Optimization. John Wiley & Sons, Inc., Hoboken, NJ, 2012

    2012

  28. [28]

    Szemer´ edi

    E. Szemer´ edi. Regular partitions of graphs. InProbl` emes combinatoires et th´ eorie des graphes (Colloq. Internat. CNRS, Univ. Orsay, Orsay, 1976), volume 260 ofColloq. Internat. CNRS, pages 399–401. CNRS, Paris, 1978

    1976

  29. [29]

    V. G. Vizing. The chromatic class of a multigraph.Kibernetika (Kiev), 1965(3):29–39, 1965

    1965

  30. [30]

    V. G. Vizing. Critical graphs with given chromatic class.Diskret. Analiz No., 5:9–17, 1965

    1965

  31. [31]

    V. G. Vizing. Some unsolved problems in graph theory.Uspehi Mat. Nauk, 23(6 (144)):117–134, 1968. 68

    1968