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.
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:
- 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.
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.
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:
- If k = 2n − 1, then G is the complete graph K2n, and hence 1-factorable (see above).
- If k = 2n − 2, then G can be constructed by removing a perfect matching from K2n. Again, G is 1-factorable.
- Chetwynd & Hilton (1985) show that if k ≥ 12n/7, then G is 1-factorable.
- 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.
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. This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of K2k+1.
- Harary (1969), Theorem 9.2, p. 85. Diestel (2005), Corollary 2.1.3, p. 37.
- Harary (1969), Theorem 9.1, p. 85.
- Chetwynd & Hilton (1985). Niessen (1994). Perkovic & Reed (1997). West.
- Petersen (1891), §9, p. 200. Harary (1969), Theorem 9.9, p. 90. See Diestel (2005), Corollary 2.1.5, p. 39 for a proof.
- Petersen (1891), §6, p. 198.
- Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, Section 5.1: "Matchings".
- Chetwynd, A. G.; Hilton, A. J. W. (1985), "Regular graphs of high degree are 1-factorizable", Proceedings of the London Mathematical Society 50 (2): 193–206, doi:10.1112/plms/s3-50.2.193.
- Diestel, Reinhard (2005), Graph Theory (3rd ed.), Springer, ISBN 3-540-26182-6, Chapter 2: "Matching, covering and packing". Electronic edition.
- Harary, Frank (1969), Graph Theory, Addison-Wesley, ISBN 0-201-02787-9, Chapter 9: "Factorization".
- Hazewinkel, Michiel, ed. (2001), "One-factorization", Encyclopedia of Mathematics, Springer, ISBN 978-1-55608-010-4
- Niessen, Thomas (1994), "How to find overfull subgraphs in graphs with large maximum degree", Discrete Applied Mathematics 51 (1–2): 117–125, doi:10.1016/0166-218X(94)90101-5.
- Perkovic, L.; Reed, B. (1997), "Edge coloring regular graphs of high degree", Discrete Mathematics, 165–166: 567–578, doi:10.1016/S0012-365X(96)00202-6.
- Petersen, Julius (1891), "Die Theorie der regulären graphs", Acta Mathematica 15: 193–220, doi:10.1007/BF02392606.
- West, Douglas B. "1-Factorization Conjecture (1985?)". Open Problems – Graph Theory and Combinatorics. Retrieved 2010-01-09.
- Weisstein, Eric W., "Graph Factor", MathWorld.
- Weisstein, Eric W., "k-Factor", MathWorld.
- Weisstein, Eric W., "k-Factorable Graph", MathWorld.