Revision as of 13:27, 10 September 2015 edit DerPhimor (talk \| contribs) 2 edits →1-factorization: I removed the statement that 1-factorability implies regularity of a graph. Tag: Visual edit ← Previous edit		Revision as of 16:08, 10 September 2015 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,647 edits Undid revision 680372416 by DerPhimor (talk) you're confusing "has a 1-factor" (=perfect matching) with "has a 1-factorization" (=partition into perfect matchings) Next edit →
Line 7: ==1-factorization== ~~Many~~If a graph is 1-factorable, ~~but~~then ~~not~~it ~~all~~has to be a [[~~Regular~~regular graph~~\|regular~~]]. 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'' − 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>

Graph factorization: Difference between revisions