## 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.

Send comments to Bojan.Mohar@uni-lj.si

##### Revised: marec 07, 2002.