Edge coloring regular graphs of high degree (Q1356779): Difference between revisions

There is an old conjecture to the effect that if \(G= (V, E)\) is a \(\Delta\)-regular simple graph of even order with \(| V|\leq 2\Delta\), then \(G\) is 1-factorizable. The authors show that this conjecture is true for large graphs with \(| V|<(2-\varepsilon)\Delta\) where \(\varepsilon> 0\). The proof is constructive and implies an algorithm for \(\Delta\)-edge-colorings of such graphs. This result improves that of \textit{A. G. Chetwynd} and \textit{A. J. W. Hilton} [1-factorizing regular graphs of high degree---an improved bound, Discrete Math. 75, No. 1-3, 103-112 (1989; Zbl 0675.05030)] for simple \(\Delta\)-regular graphs with \(\Delta\geq .5(\sqrt 7-1)| V|\).