Graph factorization

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 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 perfect matching, and a 1-factorization of a ''k''-regular graph is an edge coloring with ''k'' colors. A 2-factor is a collection of cycles that spans all vertices of the graph.

1-factorization

If a graph is 1-factorable (ie, has a 1-factorization), then it has 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. 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 below).
However, there are also ''k''-regular graphs that have chromatic index ''k'' + 1, and these graphs are not 1-factorable; examples of such graphs include:
* Any regular graph with an odd number of nodes.
* The Petersen graph.

Complete graphs

A 1-factorization of a complete graph corresponds to pairings in a round-robin tournament. The 1-factorization of complete graphs is a special case of Baranyai's theorem concerning the 1-factorization of complete hypergraphs.

One method for constructing a 1-factorization of a complete graph on an even number of vertices involves placing all but one of the vertices on a circle, forming a regular polygon, with the remaining vertex at the center of the circle. With this arrangement of vertices, one way of constructing a 1-factor of the graph is to choose an edge ''e'' from the center to a single polygon vertex together with all possible edges that lie on lines perpendicular to ''e''. The 1-factors that can be constructed in this way form a 1-factorization of the graph.

The number of distinct 1-factorizations of ''K''₂, ''K''₄, ''K''₆, ''K''₈, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... .

1-factorization conjecture

Let ''G'' be a ''k''-regular graph with 2''n'' nodes. If ''k'' is sufficiently large, it is known that ''G'' has to be 1-factorable:
* If ''k'' = 2''n'' − 1, then ''G'' is the complete graph ''K''_2''n'', and hence 1-factorable (see above).
* If ''k'' = 2''n'' − 2, then ''G'' can be constructed by removing a perfect matching from ''K''_2''n''. Again, ''G'' is 1-factorable.
* show that if ''k'' ≥ 12n/7, then ''G'' is 1-factorable.
The 1-factorization conjecture is a long-standing conjecture that states that ''k'' ≈ ''n'' is sufficient. In precise terms, the conjecture is:
* If ''n'' is odd and ''k'' ≥ ''n'', then ''G'' is 1-factorable. If ''n'' is even and ''k'' ≥ ''n'' − 1 then ''G'' is 1-factorable.
The overfull conjecture implies the 1-factorization conjecture.

Perfect 1-factorization

A perfect pair from a 1-factorization is a pair of 1-factors whose union induces a Hamiltonian cycle.

A perfect 1-factorization (P1F) of a graph is a 1-factorization having the property that every pair of 1-factors is a perfect pair. A perfect 1-factorization should not be confused with a perfect matching (also called a 1-factor).

In 1964, Anton Kotzig conjectured that every complete graph ''K''_2''n'' where ''n'' ≥ 2 has a perfect 1-factorization. So far, it is known that the following graphs have a perfect 1-factorization:

* the infinite family of complete graphs ''K''_2''p'' where ''p'' is an odd prime (by Anderson and also Nakamura, independently),
* the infinite family of complete graphs ''K''_{''p'' + 1} where ''p'' is an odd prime,
* and sporadic additional results, including ''K''_2''n'' where 2''n'' ∈ . Some newer results are collecte
here

If the complete graph ''K''_{''n'' + 1} has a perfect 1-factorization, then the complete bipartite graph ''K''_''n'',''n'' also has a perfect 1-factorization.

2-factorization

If a graph is 2-factorable, then it has to be 2''k''-regular for some integer ''k''. Julius Petersen showed in 1891 that this necessary condition is also sufficient: any 2''k''-regular graph is 2-factorable.

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., §6, p. 198. 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 graphs 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 cycle and this special case is the problem of Hamiltonian decomposition) but the general case remains unsolved.

References

Bibliography

*, Section 5.1: "Matchings".
*.
*, Chapter 2: "Matching, covering and packing"
Electronic edition

*, Chapter 9: "Factorization".
*
*.
*.
*.
*
*
*
*

Further reading

*.
{{refend

Graph theory objects
factorization