Id: arxiv/2607.02270 Url: https://arxiv.org/abs/2607.02270 Tags: math.CO Score: 0 Title: Towards the Overfull Conjecture II Domain: math.CO Source: arxiv Authors: Guantao Chen, Jessica McDonald, Songling Shan Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-07-02 Page: https://delphi.science/r/arxiv/2607.02270 Let $G$ be a simple graph with maximum degree $Δ(G)$. A subgraph $H\subseteq G$ is $Δ(G)$-overfull if $|E(H)|>Δ(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 $Δ(G)$-overfull subgraph, then $G$ cannot be edge-colored with only $Δ(G)$ colors. By Vizing's Theorem, $χ'(G)\le Δ(G)+1$, and hence $G$ is class $2$. In 1986, Chetwynd and Hilton conjectured that whenever $Δ(G)>|V(G)|/3$, the converse also holds: every class $2$ graph $G$ contains a…