Content deleted Content added
Added unsolved mathematics card (as this page is listed on that one) |
|||
| (6 intermediate revisions by 4 users not shown) | |||
Line 1:
{{Short description|Partition of a graph into spanning subgraphs}}
{{Distinguish|Factor graph}}
Line 31 ⟶ 32:
* 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.
The conjecture was confirmed by Csaba, Kühn, Lo, Osthus and Treglown for sufficiently large ''n''.<ref name="csaba">
{{Citation
| last1 = Csaba
| first1 = Béla
| last2 = Kühn
| first2 = Daniela
| last3 = Lo
| first3 = Allan
| last4 = Osthus
| first4 = Deryk
| last5 = Treglown
| first5 = Andrew
| title = Proof of the 1-factorization and Hamilton decomposition conjectures
| journal = Memoirs of the American Mathematical Society
| date = June 2016
| doi = 10.1090/memo/1154
}}
</ref>
===Perfect 1-factorization===
Line 84 ⟶ 104:
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: [[2-factor theorem|any 2''k''-regular graph is 2-factorable]].<ref>{{harvtxt|Petersen|1891}}, §9, p. 200. {{harvtxt|Harary|1969}}, Theorem 9.9, p. 90. See {{harvtxt|Diestel|2005}}, Corollary 2.1.5, p. 39 for a proof.</ref>
If a [[connectivity (graph theory)|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]].<ref>{{harvtxt|Petersen|1891}}, §6, p. 198.</ref> This applies only to connected graphs; disconnected [[counterexample]]s include disjoint unions of odd cycles, or of copies of ''K''<sub>2''k''
The [[Oberwolfach problem]] concerns the existence of 2-factorizations of complete graphs into [[graph isomorphism|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 problem|open]].
| |||