4
$\begingroup$

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

$\endgroup$

2 Answers 2

4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Sonny
    Apr 28, 2011 at 23:24
4
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Emil, yes. I was aware of that. Unfortunately, the graphs that I am working with are far from being bipartite... $\endgroup$
    – Sonny
    Apr 28, 2011 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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