# Graph factorization
> Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Graph_factorization
> Markdown URL: https://mediated.wiki/source/Graph_factorization.md
> Source: https://en.wikipedia.org/wiki/Graph_factorization
> Source revision: 1344232031
> License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/)
{{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](/source/Desargues_graph): each color class is a {{nowrap|1-factor}}.]]
[[Image:Petersen-graph-factors.svg|right|thumb|200px|The [Petersen graph](/source/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](/source/graph_theory), a '''factor''' of a [graph](/source/graph_(discrete_mathematics)) ''G'' is a [spanning subgraph](/source/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](/source/Regular_graph) 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](/source/perfect_matching), and a 1-factorization of a ''k''-regular graph is a [proper edge coloring](/source/edge_coloring) with ''k'' colors. A '''2-factor''' is a collection of disjoint [cycle](/source/cycle_(graph_theory))s that spans all vertices of the graph.
==1-factorization==
If a graph is 1-factorable then it has to be a [regular graph](/source/regular_graph). However, not all regular graphs are 1-factorable. A ''k''-regular graph is 1-factorable if it has [chromatic index](/source/chromatic_index) ''k''; examples of such graphs include:
* Any regular [bipartite graph](/source/bipartite_graph).[{{harvtxt|Harary|1969}}, Theorem 9.2, p. 85. {{harvtxt|Diestel|2005}}, Corollary 2.1.3, p. 37.] [Hall's marriage theorem](/source/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](/source/complete_graph) with an [even](/source/parity_(mathematics)) number of nodes (see below).[{{harvtxt|Harary|1969}}, Theorem 9.1, p. 85.]
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 [odd](/source/parity_(mathematics)) number of nodes.
* The [Petersen graph](/source/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](/source/heptagon) together with all possible perpendicular edges]]
A 1-factorization of a [complete graph](/source/complete_graph) corresponds to pairings in a [round-robin tournament](/source/round-robin_tournament). The 1-factorization of complete graphs is a special case of [Baranyai's theorem](/source/Baranyai's_theorem) concerning the 1-factorization of complete [hypergraph](/source/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](/source/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 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'''[{{harvtxt|Chetwynd|Hilton|1985}}. {{harvtxt|Niessen|1994}}. {{harvtxt|Perkovic|Reed|1997}}. West.] is a long-standing [conjecture](/source/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](/source/overfull_conjecture) implies the 1-factorization conjecture.
The conjecture was confirmed by Csaba, Kühn, Lo, Osthus and Treglown for sufficiently large ''n''.[
{{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
}}
]
===Perfect 1-factorization===
A '''perfect pair''' from a 1-factorization is a pair of 1-factors whose union [induces](/source/Glossary_of_graph_theory) a [Hamiltonian cycle](/source/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](/source/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:[
{{Citation
| first = W. D. | last = Wallis
| title = One-factorizations
| publisher = [Springer US](/source/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
}}
]
* the infinite family of complete graphs ''K''2''p'' where ''p'' is an odd [prime](/source/prime_number) (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](/source/complete_bipartite_graph) ''K''''n'',''n'' also has a perfect 1-factorization.[
{{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
}}
]
==2-factorization==
If a graph is 2-factorable, then it has to be 2''k''-regular for some integer ''k''. [Julius Petersen](/source/Julius_Petersen) showed in 1891 that this necessary condition is also sufficient: [any 2''k''-regular graph is 2-factorable](/source/2-factor_theorem).[{{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.]
If a [connected graph](/source/connectivity_(graph_theory)) 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](/source/Euler_tour).[{{harvtxt|Petersen|1891}}, §6, p. 198.] This applies only to connected graphs; disconnected [counterexample](/source/counterexample)s include disjoint unions of odd cycles, or of copies of ''K''2''k''+1.
The [Oberwolfach problem](/source/Oberwolfach_problem) concerns the existence of 2-factorizations of complete graphs into [isomorphic](/source/graph_isomorphism) 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](/source/Hamiltonian_cycle) and this special case is the problem of [Hamiltonian decomposition](/source/Hamiltonian_decomposition)) but the general case remains [open](/source/open_problem).
==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](/source/Springer_Science%2BBusiness_Media)
| 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](/source/Discrete_Mathematics_(journal))
| 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](/source/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](/source/Discrete_Mathematics_(journal))
| 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
---
Adapted from the Wikipedia article [Graph factorization](https://en.wikipedia.org/wiki/Graph_factorization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Graph_factorization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.