{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-02","reactions":{}}