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

About 10 years old · traced to

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.

References

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.