Graph factorization: Difference between revisions

Revision as of 13:01, 18 May 2018

Revision as of 13:05, 18 May 2018

Line 3:

[[Image:Desargues graph 3color edge.svg|thumb|200px|1-factorization of [[Desargues graph]]: each color class is a 1-factor.]]

[[Image:Petersen-graph-factors.svg|right|thumb|200px|[[Petersen graph]] can be partitioned into a 1-factor (red) and a 2-factor (blue). However, the graph is not 1-factorable.]]

In [[graph theory]], a '''factor''' of a graph ''G'' is a [[spanning subgraph]], i.e., a subgraph that has the same vertex set as ''G''. A '''''k''-factor''' of a graph is a spanning ''k''-[[Regular graph|regular]] subgraph, and a '''''k''-factorization''' partitions the edges of the graph into disjoint ''k''-factors. A graph ''G'' is said to be '''''k''-factorable''' if it admits a ''k''-factorization. In particular, a '''1-factor''' is a [[perfectMatching (graph theory)|matching]], and a 1-factorization of a ''k''-[[regular graph]] is an [[edge coloring]] with ''k'' colors. A '''2-factor''' is a collection of [[Cycle (graph theory)|cycles]] that spans all vertices of the graph.

==1-factorization==