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)?
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
0
|
|
|
|
|
3
|
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 |
|||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
3
|
Perhaps you already know this, but every bipartite regular graph is 1-factorable (see e.g. these lecture notes). |
|||
|
