Graph factorization: Difference between revisions

Revision as of 11:55, 7 November 2016

Revision as of 13:42, 7 November 2016

Line 7:

==1-factorization==

If a graph is 1-factorable, then it canhas to be a [[regular graph]]. However, not all regular graphs are 1-factorable. A ''k''-regular graph is 1-factorable if it has [[chromatic index]] ''k''; examples of such graphs include:

* Any regular [[bipartite graph]].<ref>{{harvtxt|Harary|1969}}, Theorem 9.2, p. 85. {{harvtxt|Diestel|2005}}, Corollary 2.1.3, p. 37.</ref> [[Hall's marriage theorem]] can be used to show that a ''k''-regular bipartite graph contains a perfect matching. One can then remove the perfect matching to obtain a (''k''&nbsp;&minus;&nbsp;1)-regular bipartite graph, and apply the same reasoning repeatedly.

* Any [[complete graph]] with an even number of nodes (see [[#Complete graphs|below]]).<ref>{{harvtxt|Harary|1969}}, Theorem 9.1, p. 85.</ref>