Graph factorization: Difference between revisions

Revision as of 00:29, 7 March 2024

Latest revision as of 07:53, 19 June 2025

(10 intermediate revisions by 7 users not shown)

Line 1:

{{Short description|Partition of a graph into spanning subgraphs}}

{{Distinguish|Factor graph}}

[[Image:Desargues graph 3color edge.svg|thumb|200px|1-factorization of the [[Desargues graph]]: each color class is a {{nowrap|1-factor}}.]]

[[Image:Petersen-graph-factors.svg|right|thumb|200px|The [[Petersen graph]] can be partitioned into a {{nowrap|1-factor}} (red) and a {{nowrap|2-factor}} (blue). However, the graph is not {{nowrap|1-factorable}}.]]

{{unsolved|mathematics|'''Conjecture:''' 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.}}
In [[graph theory]], a '''factor''' of a [[graph (discrete mathematics)|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 graph|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 [[edge coloring|proper edge coloring]] with ''k'' colors. A '''2-factor''' is a collection of disjoint [[cycle (graph theory)|cycle]]s that spans all vertices of the graph.

==1-factorization==

Line 30 ⟶ 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 81 ⟶ 102:

==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: [[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''_{2''k''&hairsp;+1}.

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]].

Line 122 ⟶ 143:

}}.

*{{citation

| last=Diestel | first=Reinhard | author-link = Reinhard Diestel

| title=Graph Theory

| publisher=[[Springer Science+Business Media|Springer]]