Graph factorization: Difference between revisions

Revision as of 20:49, 7 January 2010

Latest revision as of 07:53, 19 June 2025

(80 intermediate revisions by 39 users not shown)

Line 1:

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

{{cleanup}}

{{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:Hamiltonian pathPetersen-graph-factors.svg|right|thumb|200px|AnyThe [[HamiltonianPetersen cyclegraph]] iscan alsobe 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 ana [[edge coloring|proper edge coloring]] with ''k'' colors. A '''2-factor''' is a collection of disjoint [[Cyclecycle (graph theory)|cyclescycle]]s 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''&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]].

* [[Petersen graph]] – this graph can be partitioned into a 1-factor and a 2-factor, but it cannot be partitioned into three 1-factors.

===Complete graphs===

[[ImageFile:1FactK8Complete-edge-coloring.svg|thumb|200px|An easy to generate 1-factorization of ''K''₈. Eachin setwhich ofeach edges{{nowrap|1-factor}} withconsists theof samean coloredge isfrom athe 1-factor.center (Theto blacka linesvertex depictof thea original[[heptagon]] circletogether andwith areall notpossible partperpendicular of a factorization.)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.

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.

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.

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.

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

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

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

===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:

In 1985, Chetwynd and Hilston posited a stronger version of a long-standing conjecture of unknown origin called the 1-Factorization Conjecture.<ref> Niessen, Thomas, How to find overfull subgraphs in graphs with large maximum degree. 2nd Twente Workshop on Graphs and Combinatorial Optimization (Enschede, 1991). Discrete Appl. Math. 51 (1994), no. 1-2, 117--125. MR 95d:05125 97k:05084 Perkovic, L.; Reed, B. Edge coloring regular graphs of high degree. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165/166 (1997), 567--578.</ref>

* 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

:If G is a regular graph of order 2n such that <math>\Delta (G) \geq 2\lfloor \dfrac{n+1}{2} \rfloor -1</math>, then G is 1-factorable.

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

==Notes==

{{reflist}}

==References==

{{reflist}}

* {{citation

| last=Harary | first=Frank

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

Line 46 ⟶ 157:

| isbn=0-201-02787-9

}}, Chapter 9: "Factorization".

* {{springer|title=One-factorization|id=p/o110070}}

* {{citation

*{{citation

| last1=Bondy | first1=John Adrian | authorlink1=John Adrian Bondy

| last=Niessen | first=Thomas

| last2=Murty | first2=U. S. R. | authorlink2=U. S. R. Murty

| title=GraphHow Theoryto find overfull subgraphs in graphs with Applicationslarge maximum degree

| journal=Discrete Applied Mathematics

| year=1976

| volume=51

| publisher=North-Holland

| number=1–2

| isbn=0-444-19451-7

| year=1994

| url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

| pages=117–125

}}, Section 5.1: "Matchings".

| doi=10.1016/0166-218X(94)90101-5

*{{Citation

| doi-access=

| last=Diestel | first=Reinhard

}}.

| title=Graph Theory

*{{citation

| publisher=[[Springer Science+Business Media|Springer]]

| last1=Perkovic | first1=L.

| year=2005

| last2=Reed | first2=B. | author2-link=Bruce Reed (mathematician)

| edition=3rd

| title=Edge coloring regular graphs of high degree

| isbn=3-540-26182-6

| journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]

}}, Chapter 2: "Matching, covering and packing". [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Electronic edition].

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