Graph factorization: Difference between revisions

Revision as of 13:05, 18 May 2018

Revision as of 13:20, 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 [[Matchingperfect (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==

Line 84:

If a connected graph is 2''k''-regular and has an even number of edges it may also be ''k''-factored, by choosing each of the two factors to be an alternating subset of the edges of an [[Euler tour]].<ref>{{harvtxt|Petersen|1891}}, §6, p. 198.</ref> This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of ''K''_2''k''+1.

The [[Oberwolfach problem]] concerns the existence of 2-factorizations of [[complete graph]]s into isomorphic subgraphs. It asks for which subgraphs this is possible. This is known when the subgraph is connected (in which case it is a [[Hamiltonian pathcycle]] and this special case is the problem of [[Hamiltonian decomposition]]) but the general case remains unsolved.

==Notes==