An application of Tutte’s Theorem to 1-factorization of regular graphs of high degree

A well known conjecture in graph theory states that every regular graph of even order 2n2n and degree λ(2n)λ(2n), where λ≥1/2λ≥1/2, is 1-factorizable. Chetwynd and Hilton [A.G. Chetwynd, A.J.W. Hilton, 1-factorizing regular graphs of high degree — An improved bound, Discrete Math. 75 (1989) 103–112] and, independently, Niessen and Volkmann [T. Niessen, L. Volkmann, Class 1 conditions depending on the minimum degree and the number of vertices of maximum degree, J. Graph Theory (2) 14 (1990) 225–246] proved the above conjecture under the assumption that λ≥7−12≈5/6. Since these results were published no significant or even partial improvement has been made in terms of lowering the bound on λλ. We shall obtain here a partial improvement on λλ. Specifically, using the original Chetwynd–Hilton approach and Tutte’s 1-Factor Theorem, we show that the above bound can be improved to λ>57−36≈3/4, apart (possibly) from two families of exceptional cases. We then show, under the stronger assumption that λ≥λ∗≈0.785λ≥λ∗≈0.785, that one of the two families of exceptional cases cannot occur.