# when does a regular graph have a 1-factorization?

Is there a sufficient condition for a regular graph to have a 1-factorization (i.e. being able to pack all of its edges into disjoint perfect matchings, and excluding one vertex if the number of vertices is odd)?

Being a complete graph on an even number of vertices is a sufficient condition. This being said, testing whether a 3-regular graph is 3-edge-colorable is NP-hard ( http://dx.doi.org/10.1016/j.ipl.2008.05.015 )

You can have certificates that a graph requires more than 3 colors by computing its fractional chromatic index (feasible in polynomial time with a LP solver and a maximum weighted matching algorithm at hand). This is checking whether your graph contains an overfull subgraph ( http://en.wikipedia.org/wiki/Overfull_graph )

For this, you can have a look at :

Daniel Ullman and Edward Scheinerman - Fractional Graph Theory

http://www.ams.jhu.edu/~ers/fgt/fgt.pdf

Nathann

• Nathann, thanks for the answer. But, I am not looking for a sufficient and necessary condition, just a sufficient condition. Like, for instance, Dirac's theorem (or all its generalizations) for Hamiltonicity. – Sonny Apr 28 '11 at 23:24

Perhaps you already know this, but every bipartite regular graph is 1-factorable (see e.g. these lecture notes).

• Emil, yes. I was aware of that. Unfortunately, the graphs that I am working with are far from being bipartite... – Sonny Apr 28 '11 at 23:24