Content deleted Content added
m Added a reference (EOM). |
|||
| (47 intermediate revisions by 28 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==
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|
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 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''<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 30 ⟶ 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 [[Glossary of graph theory#Subgraphs|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''<sub>2''n''</sub> where ''n'' ≥ 2 has a perfect 1-factorization. So far, it is known that the following graphs have a perfect 1-factorization:<ref name="wallis">
{{Citation
| first = W. D. | last = Wallis
| title = One-factorizations
| publisher = [[Springer US]]
| series = Mathematics and Its Applications
| volume = 390
| edition = 1
| year = 1997
| chapter = 16. Perfect Factorizations
| page = 125
| doi = 10.1007/978-1-4757-2564-3_16
| isbn = 978-0-7923-4323-3
}}
</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''+1</sub> where ''p'' is an odd prime,
* 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''+1</sub> has a perfect 1-factorization, then the [[complete bipartite graph]] ''K''<sub>''n'',''n''</sub> also has a perfect 1-factorization.<ref name="wanless">
{{Citation
| last1 = Bryant
| first1 = Darryn
| last2 = Maenhaut
| first2 = Barbara M.
| last3 = Wanless
| first3 = Ian M.
| title = A Family of Perfect Factorisations of Complete Bipartite Graphs
| journal = Journal of Combinatorial Theory
| series = A
| volume = 98
| issue = 2
| pages = 328–342
| date = May 2002
| issn = 0097-3165
| doi = 10.1006/jcta.2001.3240
| doi-access= free
}}
</ref>
==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]].
==References==
{{reflist}}
==Bibliography==
{{refbegin}}
*{{citation
|
|first1 = John Adrian
|author-link1 = John Adrian Bondy
|last2 = Murty
|first2 = U. S. R.
|author-link2 = U. S. R. Murty
|title = Graph Theory with Applications
|year = 1976
|publisher = North-Holland
|isbn = 0-444-19451-7
|url = https://archive.org/details/graphtheorywitha0000bond
|url-status = dead
|url-access = registration
|access-date = 2019-12-18
|archive-url = https://web.archive.org/web/20100413104345/http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html
|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 67 ⟶ 143:
}}.
*{{citation
| last=Diestel | first=Reinhard | author-link = Reinhard Diestel
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
Line 75 ⟶ 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 91 ⟶ 167:
| pages=117–125
| doi=10.1016/0166-218X(94)90101-5
| doi-access=
}}.
*{{citation
| last1=Perkovic | first1=L.
Line 101 ⟶ 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 109 ⟶ 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 115 ⟶ 195:
| title=1-Factorization Conjecture (1985?)
| work=Open Problems – Graph Theory and Combinatorics
|
| ref=West1FC
}}
Line 126 ⟶ 206:
{{refbegin}}
*{{citation
| last=Plummer | first=Michael D. |
| title=Graph factors and factorization: 1985–2003: A survey
| journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]
Line 134 ⟶ 214:
| pages=791–821
| doi=10.1016/j.disc.2005.11.059
| doi-access=
}}.
{{refend}}
[[Category:Graph theory objects]]
[[Category:Factorization]]
| |||