Graph factorization

Not to be confused with Factor graph.
1-factorization of Desargues graph: each color class is a 1-factor.
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 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, 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:

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:

Complete graphs

1-factorization of K8 in which each 1-factor consists of an edge from the center to a vertex of a heptagon together with all possible perpendicular edges

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 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 K2, K4, K6, K8, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... A000438.

1-factorization conjecture

Let G be a k-regular graph with 2n nodes. If k is sufficiently large, it is known that G has to be 1-factorable:

The 1-factorization conjecture[3] is a long-standing conjecture that states that k  n is sufficient. In precise terms, the conjecture is:

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 K2n where n ≥ 2 has a perfect 1-factorization. So far, it is known that the following graphs have a perfect 1-factorization:[4]

If the complete graph Kn + 1 has a perfect 1-factorization, then the complete bipartite graph Kn,n also has a perfect 1-factorization.[5]

2-factorization

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

If a connected graph is 2k-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.[7] This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of K2k+1.

Notes

  1. Harary (1969), Theorem 9.2, p. 85. Diestel (2005), Corollary 2.1.3, p. 37.
  2. Harary (1969), Theorem 9.1, p. 85.
  3. Chetwynd & Hilton (1985). Niessen (1994). Perkovic & Reed (1997). West.
  4. Wallis, W. D. (1997), "16. Perfect Factorizations", One-factorizations, Mathematics and Its Applications 390 (1 ed.), Springer US, p. 125, doi:10.1007/978-1-4757-2564-3_16, ISBN 978-0-7923-4323-3
  5. Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (May 2002), "A Family of Perfect Factorisations of Complete Bipartite Graphs", Journal of Combinatorial Theory, A 98 (2): 328–342, doi:10.1006/jcta.2001.3240, ISSN 0097-3165
  6. Petersen (1891), §9, p. 200. Harary (1969), Theorem 9.9, p. 90. See Diestel (2005), Corollary 2.1.5, p. 39 for a proof.
  7. Petersen (1891), §6, p. 198.

References

Further reading

This article is issued from Wikipedia - version of the Thursday, September 10, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.