Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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|improve this question
add comment

2 Answers 2

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

share|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
add comment

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

share|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
add comment

Your Answer

 
discard

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.