In graph theory, a factor of a graphG 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 indexk; examples of such graphs include:
Any regularbipartite 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 -regular bipartite graph, and apply the same reasoning repeatedly.
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 edgee 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,....
A perfect pair from a 1-factorization is a pair of 1-factors whose unioninduces a Hamiltonian cycle. A perfect 1-factorization 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. 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:
the infinite family of complete graphs K2p where p is an odd prime,
the infinite family of complete graphs Kp + 1 where p is an odd prime,
and sporadic additional results, including K2n where 2n ∈. Some newer results are collected .
If the complete graph Kn + 1 has a perfect 1-factorization, then the complete bipartite graphKn,n also has a perfect 1-factorization.
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. 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. 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 but the general case remains unsolved.
