## One Factorization and Hamiltonian Factorization Conjecture

An old conjecture, probably going back to G. A. Dirac in the 1950's, states that regular graphs of large degree are Class 1 (with respect to edge-colorings):

The One Factorization Conjecture: Let G be a k-regular graph of even order n, where k is at least n/2. Then G is 1-factorable.

Chetwynd and Hilton [1] proved the conjecture under a stronger assumption that k is at least cn/2, where c is equal to the square root of 7 minus 1 (approximately 1.646). Tony Hilton (private communication) reports some further improvements (smaller constant c).

This conjecture has a counterpart where it is not required that the graph G is regular.

Another direction would be to consider total colorings of graphs whose minimum degree is large. For an example see [2].

Nash-Williams [3] proposed a strenthening of the One Factorization Conjecture in another direction:

Hamiltonian Factorization Conjecture: Let G be a k-regular graph of order n, where k is at least n/2. Then G has a hamiltonian factorization, i.e., the edge-set of G can be partitioned into k/2 hamilton cycles (if k is even) or into (k - 1)/2 hamilton cycles and a 1-factor (if k is odd).

References:

[1] A. G. Chetwynd, A. J. W. Hilton, 1-factorizing regular graphs of high degree: an improved bound, Discrete Math. 75 (1989) 103-112.

[2] B.-L. Chen, H.-L. Fu, Total colorings of graphs of order 2n having maximum degree 2n - 2, Graphs Combin. 8 (1992) 119-123.

[3] C. St. J. A. Nash-Williams, Hamilton arcs and circuits, Recent trends in Graph theory, Lecture Notes in Math. 186, Springer, 1971, pp. 197-210.