The Overfull Conjecture for graphs of maximum degree greater than one third their order

Let GG be a simple graph. Write Δ(G)\Delta(G) for its maximum degree, and call GG overfull if

E(G)>Δ(G)V(G)2.|E(G)|>\Delta(G)\left\lfloor\frac{|V(G)|}{2}\right\rfloor.

A graph is of Class 2 when its chromatic index satisfies χ(G)=Δ(G)+1\chi'(G)=\Delta(G)+1.

Overfull Conjecture. Let GG be a graph of Class 22 with

Δ(G)>V(G)3.\Delta(G)>\frac{|V(G)|}{3}.

Then GG contains an overfull subgraph HH with Δ(H)=Δ(G)\Delta(H)=\Delta(G).

This conjecture of Chetwynd and Hilton would make determining the chromatic index polynomial-time solvable for graphs with maximum degree greater than one third their order. It is known in several dense cases, including when Δ(G)V(G)3\Delta(G)\geq |V(G)|-3 and for sufficiently large graphs with Δ(G)(1ε)V(G)\Delta(G)\geq(1-\varepsilon)|V(G)| for 0<ε1/140<\varepsilon\leq 1/14, but remains open in general.

Sources & referencesView supporting material

Primary source

Xuli Qi, Chunhui Ge and Yanrui Feng, “A new improvement to the Overfull Conjecture”, arXiv:2512.07044 (2025).

Additional references

2 papers in this index state this conjecture (2016–2025). The statement above is taken from the most recent of them; the others are arXiv:1603.05018.

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.