Content deleted Content added
| (37 intermediate revisions by 21 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''- ==1-factorization==
If a graph is 1-factorable
* Any regular [[bipartite graph]].<ref>{{harvtxt|Harary|1969}}, Theorem 9.2, p. 85. {{harvtxt|Diestel|2005}}, Corollary 2.1.3, p. 37.</ref> [[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'' − 1)-regular bipartite graph, and apply the same reasoning repeatedly.
* Any [[complete graph]] with an [[parity (mathematics)|even]] number of nodes (see [[#Complete graphs|below]]).<ref>{{harvtxt|Harary|1969}}, Theorem 9.1, p. 85.</ref>
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:
* Any regular graph with an [[parity (mathematics)|odd]] number of nodes.
* The [[Petersen graph]].
===Complete graphs===
[[File:Complete-edge-coloring.svg|thumb|200px|1-factorization of ''K''<sub>8</sub> in which each {{nowrap|1-factor}} consists of an edge from the center to a vertex of a [[heptagon]] 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 [[hypergraph]]s.
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
The number of distinct 1-factorizations of ''K''<sub>2</sub>, ''K''<sub>4</sub>, ''K''<sub>6</sub>, ''K''<sub>8</sub>, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ({{oeis|A000438}}).
===1-factorization conjecture===
Line 26 ⟶ 28:
* If ''k'' = 2''n'' − 1, then ''G'' is the complete graph ''K''<sub>2''n''</sub>, and hence 1-factorable (see [[#Complete graphs|above]]).
* If ''k'' = 2''n'' − 2, then ''G'' can be constructed by removing a perfect matching from ''K''<sub>2''n''</sub>. Again, ''G'' is 1-factorable.
* {{harvtxt|Chetwynd|Hilton|1985}} show that if ''k'' ≥
The '''1-factorization conjecture'''<ref>{{harvtxt|Chetwynd|Hilton|1985}}. {{harvtxt|Niessen|1994}}. {{harvtxt|Perkovic|Reed|1997}}. [[#West1FC|West]].</ref> is a long-standing [[conjecture]] that states that ''k'' ≈ ''n'' is sufficient. In precise terms, the conjecture is:
* 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===
A '''perfect pair''' from a 1-factorization is a pair of 1-factors whose union [[
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
{{Citation
| first = W. D. | last = Wallis
Line 52 ⟶ 73:
</ref>
* the infinite family of complete graphs ''K''<sub>2''p''</sub> where ''p'' is an odd [[prime number|prime]] (by Anderson and also Nakamura, independently),
* the infinite family of complete graphs ''K''<sub>''p''
* and sporadic additional results, including ''K''<sub>2''n''</sub> where 2''n'' ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Some newer results are collected [http://users.monash.edu.au/~iwanless/data/P1F/newP1F.html here].
<!-- Related OEIS sequences: A005702 A120488 A120489 -->
If the complete graph ''K''<sub>''n''
{{Citation
| last1 = Bryant
Line 75 ⟶ 96:
| issn = 0097-3165
| doi = 10.1006/jcta.2001.3240
| doi-access= free
}}
</ref>
Line 80 ⟶ 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
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]].
{{reflist}}▼
==References==
▲{{reflist}}
==Bibliography==
{{refbegin}}
*{{citation
|
|first1 = John Adrian
|author-link1 = John Adrian Bondy
| title=Graph Theory with Applications▼
|last2 = Murty
| year=1976▼
|first2 = U. S. R.
| publisher=North-Holland▼
|author-link2 = U. S. R. Murty
| isbn=0-444-19451-7▼
| url=http://www.math.jussieu.fr/~jabondy/books/gtwa/gtwa.html▼
|url = https://archive.org/details/graphtheorywitha0000bond
|url-status = dead
|url-access = registration
|access-date = 2019-12-18
▲ |
|archive-date = 2010-04-13
}}, Section 5.1: "Matchings".
*{{citation
| last1=Chetwynd | first1=A. G. | author1-link = Amanda Chetwynd
| last2=Hilton | first2=A. J. W.
| title=Regular graphs of high degree are 1-factorizable
Line 110 ⟶ 143:
}}.
*{{citation
| last=Diestel | first=Reinhard | author-link = Reinhard Diestel
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
Line 118 ⟶ 151:
}}, Chapter 2: "Matching, covering and packing". [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Electronic edition].
*{{citation
| last=Harary | first=Frank |
| title=Graph Theory
| publisher=Addison-Wesley
Line 134 ⟶ 167:
| pages=117–125
| doi=10.1016/0166-218X(94)90101-5
| doi-access=
▲}}.
}}.▼
*{{citation
| last1=Perkovic | first1=L.
Line 144 ⟶ 178:
| pages=567–578
| doi=10.1016/S0012-365X(96)00202-6
| doi-access=
▲}}.
}}.▼
*{{citation
| last=Petersen | first=Julius |
| title=Die Theorie der regulären graphs
| journal=[[Acta Mathematica]]
Line 152 ⟶ 187:
| year=1891
| pages = 193–220
| doi = 10.1007/BF02392606
| url=https://zenodo.org/record/2304433/files/article.pdf
}}.
*{{cite web
| last=West | first=Douglas B.
Line 158 ⟶ 195:
| title=1-Factorization Conjecture (1985?)
| work=Open Problems – Graph Theory and Combinatorics
|
| ref=West1FC
}}
Line 169 ⟶ 206:
{{refbegin}}
*{{citation
| last=Plummer | first=Michael D. |
| title=Graph factors and factorization: 1985–2003: A survey
| journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]
Line 177 ⟶ 214:
| pages=791–821
| doi=10.1016/j.disc.2005.11.059
| doi-access=
▲}}.
}}.
{{refend}}
[[Category:Graph theory objects]]
[[Category:Factorization]]
| |||