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)?
2 Answers
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
-
$\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$– SonnyApr 28, 2011 at 23:24
Perhaps you already know this, but every bipartite regular graph is 1-factorable (see e.g. these lecture notes).
-
$\begingroup$ Emil, yes. I was aware of that. Unfortunately, the graphs that I am working with are far from being bipartite... $\endgroup$– SonnyApr 28, 2011 at 23:24