Graph factorization#1-factorization
{{Distinguish|Factor graph}}
Image:Desargues graph 3color edge.svg: each color class is a {{nowrap|1-factor}}.]]
Image:Petersen-graph-factors.svg 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.{{harvtxt|Harary|1969}}, Theorem 9.2, p. 85. {{harvtxt|Diestel|2005}}, Corollary 2.1.3, p. 37. 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).{{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 number of nodes.
- The Petersen graph.
=Complete graphs=
File:Complete-edge-coloring.svg 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 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.
- {{harvtxt|Chetwynd|Hilton|1985}} show that if k ≥ 12n/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 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.
=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:
{{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
}}
- 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 [http://users.monash.edu.au/~iwanless/data/P1F/newP1F.html 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.
{{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 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.{{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 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.{{harvtxt|Petersen|1891}}, §6, p. 198. 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
{{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}}