Graph factorization

{{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 ''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.<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 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: * Any regular graph with an 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 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 ''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'''<ref>{{harvtxt|Chetwynd|Hilton|1985}}. {{harvtxt|Niessen|1994}}. {{harvtxt|Perkovic|Reed|1997}}. 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 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 (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: 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 counterexamples 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 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== {{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 | 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 | 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 | 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