Graph factorization: Difference between revisions
From HandWiki
imported>Unex link |
add |
||
| Line 1: | Line 1: | ||
[[Image:Desargues graph 3color edge.svg|thumb|200px|1-factorization of [[ | {{Short description|Partition of a graph into spanning subgraphs}} | ||
[[Image:Petersen-graph-factors.svg|right|thumb|200px|[[ | {{Distinguish|Factor graph}} | ||
In [[Graph theory|graph theory]], a '''factor''' of a 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|perfect matching]], and a 1-factorization of a ''k''- | |||
[[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|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|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== | ==1-factorization== | ||
If a graph is 1-factorable | If a graph is 1-factorable then it has to be a [[Regular graph|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|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 regular [[Bipartite graph|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|complete graph]] with an even number of nodes (see below).<ref>{{harvtxt|Harary|1969}}, Theorem 9.1, p. 85.</ref> | * Any [[Complete graph|complete graph]] with an [[Parity (mathematics)|even]] number of nodes (see 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: | 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 number of nodes. | * Any regular graph with an [[Parity (mathematics)|odd]] number of nodes. | ||
* The [[Petersen graph]]. | * The [[Petersen graph]]. | ||
===Complete graphs=== | ===Complete graphs=== | ||
[[File:Complete-edge-coloring.svg|thumb|200px|1-factorization of ''K''<sub>8</sub> in which each 1-factor consists of an edge from the center to a vertex of a [[ | [[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|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|hypergraph]]s. | A 1-factorization of a [[Complete graph|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|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 | 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|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}}. | 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=== | ===1-factorization conjecture=== | ||
| Line 24: | Line 28: | ||
* If ''k'' = 2''n'' − 1, then ''G'' is the complete graph ''K''<sub>2''n''</sub>, and hence 1-factorable (see above). | * If ''k'' = 2''n'' − 1, then ''G'' is the complete graph ''K''<sub>2''n''</sub>, and hence 1-factorable (see 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. | * 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'' ≥ | * {{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}}. West.</ref> is a long-standing [[Conjecture|conjecture]] that states that ''k'' ≈ ''n'' is sufficient. In precise terms, the conjecture is: | The '''1-factorization conjecture'''<ref>{{harvtxt|Chetwynd|Hilton|1985}}. {{harvtxt|Niessen|1994}}. {{harvtxt|Perkovic|Reed|1997}}. West.</ref> is a long-standing [[Conjecture|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. | * 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|overfull conjecture]] implies the 1-factorization conjecture. | The [[Overfull conjecture|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=== | ===Perfect 1-factorization=== | ||
| Line 34: | Line 57: | ||
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). | 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, [[Biography:Anton Kotzig|Anton Kotzig]] conjectured that every | In 1964, [[Biography:Anton Kotzig|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 | {{Citation | ||
| first = W. D. | last = Wallis | | first = W. D. | last = Wallis | ||
| Line 50: | Line 73: | ||
</ref> | </ref> | ||
* the infinite family of complete graphs ''K''<sub>2''p''</sub> where ''p'' is an odd prime (by Anderson and also Nakamura, independently), | * 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, | * 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]. | * 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 --> | <!-- 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|complete bipartite graph]] ''K''<sub>''n'',''n''</sub> also has a perfect 1-factorization.<ref name="wanless"> | If the complete graph ''K''<sub>''n''+1</sub> has a perfect 1-factorization, then the [[Complete bipartite graph|complete bipartite graph]] ''K''<sub>''n'',''n''</sub> also has a perfect 1-factorization.<ref name="wanless"> | ||
{{Citation | {{Citation | ||
| last1 = Bryant | | last1 = Bryant | ||
| Line 79: | Line 102: | ||
==2-factorization== | ==2-factorization== | ||
If a graph is 2-factorable, then it has to be 2''k''-regular for some integer ''k''. [[Biography:Julius Petersen|Julius Petersen]] showed in 1891 that this necessary condition is also sufficient: 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 graph is 2-factorable, then it has to be 2''k''-regular for some integer ''k''. [[Biography:Julius Petersen|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 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 | 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|counterexample]]s include disjoint unions of odd cycles, or of copies of ''K''<sub>2''k''+1</sub>. | ||
The [[Oberwolfach problem]] concerns the existence of 2-factorizations of [[ | 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 [[Unsolved:Open problem|open]]. | ||
==References== | ==References== | ||
| Line 117: | Line 140: | ||
}}. | }}. | ||
*{{citation | *{{citation | ||
| title=Graph Theory | | title=Graph Theory | ||
| publisher=[[Company:Springer Science+Business Media|Springer]] | | publisher=[[Company:Springer Science+Business Media|Springer]] | ||
| Line 159: | Line 181: | ||
| pages = 193–220 | | pages = 193–220 | ||
| doi = 10.1007/BF02392606| doi-access=free | | doi = 10.1007/BF02392606| doi-access=free | ||
| url=https://zenodo.org/record/2304433/files/article.pdf | |||
}}. | }}. | ||
*{{cite web | *{{cite web | ||
Latest revision as of 15:46, 13 February 2026
Short description: Partition of a graph into spanning subgraphs
 |
Unsolved problem in 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. (more unsolved problems in mathematics)
|
In graph theory, a factor of a 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 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 proper edge coloring with k colors. A 2-factor is a collection of disjoint cycles 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.[1] 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 even number of nodes (see below).[2]
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 number of nodes.
- The Petersen graph.
Complete graphs
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 hypergraphs.
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 K2, K4, K6, K8, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... (OEIS: A000438).
1-factorization conjecture
Let G be a k-regular graph with 2n nodes. If k is sufficiently large, it is known that G has to be 1-factorable:
- If k = 2n − 1, then G is the complete graph K2n, and hence 1-factorable (see above).
- If k = 2n − 2, then G can be constructed by removing a perfect matching from K2n. Again, G is 1-factorable.
- (Chetwynd Hilton) show that if k ≥ 12n/7, then G is 1-factorable.
The 1-factorization conjecture[3] 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.[4]
Perfect 1-factorization
A perfect pair from a 1-factorization is a pair of 1-factors whose union 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 K2n where n ≥ 2 has a perfect 1-factorization. So far, it is known that the following graphs have a perfect 1-factorization:[5]
- the infinite family of complete graphs K2p where p is an odd prime (by Anderson and also Nakamura, independently),
- the infinite family of complete graphs Kp+1 where p is an odd prime,
- and sporadic additional results, including K2n where 2n ∈ {16, 28, 36, 40, 50, 126, 170, 244, 344, 730, 1332, 1370, 1850, 2198, 3126, 6860, 12168, 16808, 29792}. Some newer results are collected here.
If the complete graph Kn+1 has a perfect 1-factorization, then the complete bipartite graph Kn,n also has a perfect 1-factorization.[6]
2-factorization
If a graph is 2-factorable, then it has to be 2k-regular for some integer k. Julius Petersen showed in 1891 that this necessary condition is also sufficient: any 2k-regular graph is 2-factorable.[7]
If a connected graph is 2k-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.[8] This applies only to connected graphs; disconnected counterexamples include disjoint unions of odd cycles, or of copies of K2k+1.
The Oberwolfach problem concerns the existence of 2-factorizations of complete graphs into 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.
References
- ↑ (Harary 1969), Theorem 9.2, p. 85. (Diestel 2005), Corollary 2.1.3, p. 37.
- ↑ (Harary 1969), Theorem 9.1, p. 85.
- ↑ (Chetwynd Hilton). (Niessen 1994). (Perkovic Reed). West.
- ↑ Csaba, Béla; Kühn, Daniela; Lo, Allan; Osthus, Deryk; Treglown, Andrew (June 2016), "Proof of the 1-factorization and Hamilton decomposition conjectures", Memoirs of the American Mathematical Society, doi:10.1090/memo/1154
- ↑ Wallis, W. D. (1997), "16. Perfect Factorizations", One-factorizations, Mathematics and Its Applications, 390 (1 ed.), Springer US, p. 125, doi:10.1007/978-1-4757-2564-3_16, ISBN 978-0-7923-4323-3
- ↑ Bryant, Darryn; Maenhaut, Barbara M.; Wanless, Ian M. (May 2002), "A Family of Perfect Factorisations of Complete Bipartite Graphs", Journal of Combinatorial Theory, A 98 (2): 328–342, doi:10.1006/jcta.2001.3240, ISSN 0097-3165
- ↑ (Petersen 1891), §9, p. 200. (Harary 1969), Theorem 9.9, p. 90. See (Diestel 2005), Corollary 2.1.5, p. 39 for a proof.
- ↑ (Petersen 1891), §6, p. 198.
Bibliography
- Bondy, John Adrian; Murty, U. S. R. (1976), Graph Theory with Applications, North-Holland, ISBN 0-444-19451-7, https://archive.org/details/graphtheorywitha0000bond, retrieved 2019-12-18, Section 5.1: "Matchings".
- "Regular graphs of high degree are 1-factorizable", Proceedings of the London Mathematical Society 50 (2): 193–206, 1985, doi:10.1112/plms/s3-50.2.193.
- Graph Theory (3rd ed.), Springer, 2005, ISBN 3-540-26182-6, Chapter 2: "Matching, covering and packing". Electronic edition.
- Graph Theory, Addison-Wesley, 1969, ISBN 0-201-02787-9, Chapter 9: "Factorization".
- Hazewinkel, Michiel, ed. (2001), "One-factorization", Encyclopedia of Mathematics, Springer Science+Business Media B.V. / Kluwer Academic Publishers, ISBN 978-1-55608-010-4, https://www.encyclopediaofmath.org/index.php?title=p/o110070
- Niessen, Thomas (1994), "How to find overfull subgraphs in graphs with large maximum degree", Discrete Applied Mathematics 51 (1–2): 117–125, doi:10.1016/0166-218X(94)90101-5.
- Perkovic, L. (1997), "Edge coloring regular graphs of high degree", Discrete Mathematics 165–166: 567–578, doi:10.1016/S0012-365X(96)00202-6.
- "Die Theorie der regulären graphs", Acta Mathematica 15: 193–220, 1891, doi:10.1007/BF02392606, https://zenodo.org/record/2304433/files/article.pdf.
- West, Douglas B.. "1-Factorization Conjecture (1985?)". Open Problems – Graph Theory and Combinatorics. http://www.math.uiuc.edu/~west/openp/1fact.html.
- Weisstein, Eric W.. "Graph Factor". http://mathworld.wolfram.com/GraphFactor.html.
- Weisstein, Eric W.. "k-Factor". http://mathworld.wolfram.com/k-Factor.html.
- Weisstein, Eric W.. "k-Factorable Graph". http://mathworld.wolfram.com/k-FactorableGraph.html.
Further reading
- "Graph factors and factorization: 1985–2003: A survey", Discrete Mathematics 307 (7–8): 791–821, 2007, doi:10.1016/j.disc.2005.11.059.
 |  |
