MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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)?

share|cite|improve this question

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 ( )

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 ( )

For this, you can have a look at :

Daniel Ullman and Edward Scheinerman - Fractional Graph Theory


share|cite|improve this answer
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).

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.