Edge coloring graphs with large minimum degree
Michael J. Plantholt, Songling Shan · Journal of Graph Theory · 2022
Abstract Let be a simple graph with maximum degree . A subgraph of is overfull if Chetwynd and Hilton in 1986 conjectured that a graph with has chromatic index if and only if contains no overfull subgraph. The best previous results supporting this conjecture have been obtained for regular graphs. For example, Perković and Reed verified the conjecture for large regular graphs with degree arbitrarily close to . We provide a similar result for general graphs asymptotically, showing that for any given , there exists a positive integer such that the following statement holds: if is a graph on vertices with minimum degree at least , then has chromatic index if and only if contains no overfull subgraph.