imported>Sowhates: /* 1-factorization conjecture */

2025-06-19T07:53:25Z

1-factorization conjecture

New page

{{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 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]].<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''8 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 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, ... ({{oeis|A000438}}).

===1-factorization conjecture===
Let ''G'' be a ''k''-regular graph with 2''n'' nodes. If ''k'' is sufficiently large, it is known that ''G'' has to be 1-factorable:
* If ''k'' = 2''n'' − 1, then ''G'' is the complete graph ''K''2''n'', 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''2''n''. Again, ''G'' is 1-factorable.
* {{harvtxt|Chetwynd|Hilton|1985}} show that if ''k'' ≥ 12''n''/7, then ''G'' is 1-factorable.
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''2''n'' 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''2''p'' where ''p'' is an odd [[prime number|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''2''n'' 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].


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.<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 [[counterexample]]s include disjoint unions of odd cycles, or of copies of ''K''2''k''+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]].

==References==
{{reflist}}

==Bibliography==
{{refbegin}}
*{{citation
|last1 = Bondy
|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
| journal=Proceedings of the London Mathematical Society
| year=1985
| volume=50
| number=2
| pages=193–206
| doi=10.1112/plms/s3-50.2.193
}}.
*{{citation
| last=Diestel | first=Reinhard | author-link = Reinhard Diestel
| title=Graph Theory
| publisher=[[Springer Science+Business Media|Springer]]
| year=2005
| edition=3rd
| isbn=3-540-26182-6
}}, Chapter 2: "Matching, covering and packing". [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Electronic edition].
*{{citation
| last=Harary | first=Frank | author-link=Frank Harary
| title=Graph Theory
| publisher=Addison-Wesley
| year=1969
| isbn=0-201-02787-9
}}, Chapter 9: "Factorization".
* {{springer|title=One-factorization|id=p/o110070}}
*{{citation
| last=Niessen | first=Thomas
| title=How to find overfull subgraphs in graphs with large maximum degree
| journal=Discrete Applied Mathematics
| volume=51
| number=1–2
| year=1994
| pages=117–125
| doi=10.1016/0166-218X(94)90101-5
| doi-access=
}}.
*{{citation
| last1=Perkovic | first1=L.
| last2=Reed | first2=B. | author2-link=Bruce Reed (mathematician)
| title=Edge coloring regular graphs of high degree
| journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]
| volume=165–166
| year=1997
| pages=567–578
| doi=10.1016/S0012-365X(96)00202-6
| doi-access=
}}.
*{{citation
| last=Petersen | first=Julius | author-link=Julius Petersen
| title=Die Theorie der regulären graphs
| journal=[[Acta Mathematica]]
| volume=15
| year=1891
| pages = 193–220
| doi = 10.1007/BF02392606| doi-access=free
| url=https://zenodo.org/record/2304433/files/article.pdf
}}.
*{{cite web
| last=West | first=Douglas B.
| url=http://www.math.uiuc.edu/~west/openp/1fact.html
| title=1-Factorization Conjecture (1985?)
| work=Open Problems – Graph Theory and Combinatorics
| access-date=2010-01-09
| ref=West1FC
}}
*{{MathWorld | urlname=GraphFactor | title=Graph Factor}}
*{{MathWorld | urlname=k-Factor | title=k-Factor}}
*{{MathWorld | urlname=k-FactorableGraph | title=k-Factorable Graph}}
{{refend}}

==Further reading==
{{refbegin}}
*{{citation
| last=Plummer | first=Michael D. | author-link = Michael D. Plummer
| title=Graph factors and factorization: 1985–2003: A survey
| journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]
| volume=307
| number=7–8
| year=2007
| pages=791–821
| doi=10.1016/j.disc.2005.11.059
| doi-access=
}}.
{{refend}}

[[Category:Graph theory objects]]
[[Category:Factorization]]

Graph factorization - Revision history

imported>Sowhates: /* 1-factorization conjecture */