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).
[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.
Send comments to Bojan.Mohar@uni-lj.si