Graph factorization: Difference between revisions

Revision as of 23:08, 20 October 2007

Latest revision as of 07:53, 19 June 2025

(96 intermediate revisions by 43 users not shown)

Line 1:

{{Short description|Partition of a graph into spanning subgraphs}}

In [[graph theory]], a '''1-factor''' of a graph is a collection of disjoint edges, which together are incident on all the vertices of the graph (a ''[[perfect matching]]''). A '''1-factorization''' of a graph ''G'' is a collection of 1-factors such that every edge of ''G'' is in exactly one of these 1-factors. The graph is thus "factored" into edge-disjoint subgraphs; in each subgraph, each vertex is the endpoint of exactly one edge. Analogously, an '''''n''-factorization''' factors the graph into disjoint subgraphs in which each vertex is the endpoint of ''n'' edges.

{{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}}.]]

A graph ''G'' is said to be '''1-factorable''' if it admits a 1-factorization.

[[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.

==Example1-factorization==

[[Image:1FactK8.svg|thumb|An easy to generate 1-factorization of ''K''₈. Each set of edges with the same color is a 1-factor. [[User:Bobbadoc|Bobbadoc]] 23:08, 20 October 2007 (UTC)(The black lines depict the original circle and are not part of a factorization.)]]

Draw seven vertices distributed evenly around a circle, and one in the middle, for a total of eight vertices. Join the middle point to any single point on the circle; call this line ''L''. Join points to other points on the circle together [[if and only if]] they can be joined together with a line [[Orthogonality|orthogonal]] to ''L''. Since the points were arranged evenly, this will produce a matching (in fact a perfect matching) of these eight vertices.

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:

Now rotate the lines one vertex to the right: Start over again with the eight vertices as described and join the center point to the point in the circle directly clockwise from the first one chosen. Join the other points on the circle in a similar matter as before. This is again another perfect matching of these eight points.

* 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''&nbsp;&minus;&nbsp;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''&nbsp;+&nbsp;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===

Each of these perfect matchings can also be looked at as a 1-factor of the [[complete graph]] on eight vertices, <math>K_8</math>. Continuing the process above, you will form a 1-factorization of <math>K_8</math>. This is a proof that there exists a 1-factorization of <math>K_{2n}</math> for all ''n''.

[[File:Complete-edge-coloring.svg|thumb|200px|1-factorization of ''K''₈ 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.

A 1-factorization of a [[complete graph]] corresponds to pairings in a round-robin tournament.

The number of distinct 1-factorizations of ''K''₂, ''K''₄, ''K''₆, ''K''₈, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ({{oeis|A000438}}).

[[Category:Graph theory]]

===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''&nbsp;=&nbsp;2''n''&nbsp;&minus;&nbsp;1, then ''G'' is the complete graph ''K''_2''n'', and hence 1-factorable (see [[#Complete graphs|above]]).

* If ''k''&nbsp;=&nbsp;2''n''&nbsp;&minus;&nbsp;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''&nbsp;≥&nbsp;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''&nbsp;≈&nbsp;''n'' is sufficient. In precise terms, the conjecture is:

* If ''n'' is odd and ''k''&nbsp;≥&nbsp;''n'', then ''G'' is 1-factorable. If ''n'' is even and ''k''&nbsp;≥&nbsp;''n''&nbsp;&minus;&nbsp;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].

<!-- Related OEIS sequences: A005702 A120488 A120489 -->

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]]