3
$\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$
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

| cite | improve this answer | |
$\endgroup$
  • $\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 '11 at 23:24
4
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\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 '11 at 23:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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