{
  "id": "graph-factorization-636490-985ba7f0380bbf54",
  "slug": "graph-factorization",
  "title": "graph factorization",
  "qid": "Q5597083",
  "lead": ": each color class is a . can be partitioned into a (red) and a (blue). However, the graph is not . 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 a proper edge coloring with k colors. A 2-factor is a collection of disjoint cycles that spans all vertices of the graph.",
  "body": ": each color class is a . can be partitioned into a (red) and a (blue). However, the graph is not . 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 a proper edge coloring with k colors. A 2-factor is a collection of disjoint 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: 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&nbsp;&minus;&nbsp;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&nbsp;+&nbsp;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=== 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 on an even number of vertices involves placing all but one of the vertices in a regular polygon, with the remaining vertex at the center. 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 2 , K 4 , K 6 , K 8 , ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... . ===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: If k&nbsp;=&nbsp;2n&nbsp;&minus;&nbsp;1, then G is the complete graph K 2n , and hence 1-factorable (see above). If k&nbsp;=&nbsp;2n&nbsp;&minus;&nbsp;2, then G can be constructed by removing a perfect matching from K 2n . Again, G is 1-factorable. show that if k&nbsp;≥&nbsp;12n/7, then G is 1-factorable. The 1-factorization conjecture is a long-standing conjecture that states that k&nbsp;≈&nbsp;n is sufficient. In precise terms, the conjecture is: If n is odd and k&nbsp;≥&nbsp;n, then G is 1-factorable. If n is even and k&nbsp;≥&nbsp;n&nbsp;&minus;&nbsp;1 then G is 1-factorable. The overfull conjecture implies the 1-factorization conjecture. The conjecture was confirmed by Csaba, Kühn, Lo, Osthus and Treglown for sufficiently large n. ===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 2n 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 2p 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 2n where 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Some newer results are collected 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 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 K 2k+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 open. ==References== ==Bibliography== , Section 5.1: \"Matchings\". . , Chapter 2: \"Matching, covering and packing\". Electronic edition. , Chapter 9: \"Factorization\". . . . ==Further reading== .",
  "categories": [
    "23118434",
    "23603337",
    "29176373",
    "29264919",
    "48128016"
  ],
  "license": "CC BY-SA 4.0",
  "source_uri": "https://en.wikipedia.org/w/index.php?oldid=1344232031",
  "content_hash": "985ba7f0380bbf549e25cf4e5ed75dc370eae8a27a97b425e79176efae961506",
  "created_at": 1792311341.1013527,
  "updated_at": 1773890339.0,
  "claims": [],
  "contradictions": [],
  "confidence": 0.6,
  "csl": {
    "id": "graph-factorization-636490-985ba7f0380bbf54",
    "type": "webpage",
    "title": "graph factorization",
    "author": [
      {
        "family": "Anticloud FZ LLE",
        "literal": "Anticloud FZ LLE"
      }
    ],
    "container-title": "encyclopegia.org",
    "publisher": "Anticloud FZ LLE",
    "publisher-place": "Dubai, United Arab Emirates",
    "URL": "https://encyclopegia.org/a/graph-factorization",
    "issued": {
      "date-parts": [
        [
          2026,
          10,
          18
        ]
      ]
    },
    "accessed": {
      "date-parts": [
        [
          2026,
          11,
          18
        ]
      ]
    },
    "license": "CC BY-SA 4.0",
    "DOI": "eo1:graph-factorization-636490-985ba7f0380bbf54",
    "isBasedOn": "https://en.wikipedia.org/w/index.php?oldid=1344232031",
    "note": "Immutable snapshot graph-factorization-636490-985ba7f0380bbf54, content root 985ba7f0380bbf54…"
  }
}