Overfull conjecture for graphs with high minimum degree
Michael J. Plantholt · Journal of Graph Theory · 2004
Abstract Chetwynd and Hilton showed that any regular graph G of even order n which has relatively high degree $\Delta (G)\,\ge\,((\sqrt{7}- 1)/2)\, n$ has a 1‐factorization. This is equivalent to saying that under these conditions G has chromatic index equal to its maximum degree $\Delta(G)$ . Using this result, we show that any (not necessarily regular) graph G of even order n that has sufficiently high minimum degree $\delta(G)\,\ge\,(\sqrt{7}/3)\,n$ has chromatic index equal to its maximum degree providing that G does not contain an “overfull” subgraph, that is, a subgraph which trivially forces the chromatic index to be more than the maximum degree. This result thus verifies the Overfull Conjecture for graphs of even order and sufficiently high minimum degree. © 2004 Wiley Periodicals, Inc. J Graph Theory 47: 73–80, 2004