Towards the Overfull Conjecture

ABSTRACT Let be a simple graph with maximum degree denoted as . An overfull subgraph of is a subgraph satisfying the condition . In 1986, Chetwynd and Hilton proposed the Overfull Conjecture, stating that a graph with maximum degree has chromatic index equal to if and only if it does not contain any overfull subgraph. The Overfull Conjecture has many implications. For example, it implies a polynomial‐time algorithm for determining the chromatic index of graphs with , and implies several longstanding conjectures in the area of graph edge colorings. In this paper, we make a breakthrough towards the conjecture when not imposing a minimum degree condition on the graph: for any , there exists a positive integer such that if is a graph on vertices with , then the Overfull Conjecture holds for . The previous best result in this direction, due to Chetwynd and Hilton from 1989, asserts the conjecture for graphs with . Our result also implies the Average Degree Conjecture of Vizing from 1968 for the same class of graphs .