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: 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. 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: The 1-factorization conjecture 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 "K" where "n" ≥ 2 has a perfect 1-factorization. So far, it is known that the following graphs have a perfect 1-factorization: If the complete graph "K" has a perfect 1-factorization, then the complete bipartite graph "K" 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. This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of "K". 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.