The Overfull Conjecture for graphs of maximum degree greater than one third their order
The Overfull Conjecture for graphs of maximum degree greater than one third their order
Let be a simple graph. Write for its maximum degree, and call overfull if
A graph is of Class 2 when its chromatic index satisfies .
Overfull Conjecture. Let be a graph of Class with
Then contains an overfull subgraph with .
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 and for sufficiently large graphs with for , 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.