Graph factorization: Difference between revisions

Revision as of 00:46, 5 August 2020

Latest revision as of 07:53, 19 June 2025

(22 intermediate revisions by 15 users not shown)

Line 1:

{{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 (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 (ie, has a 1-factorization), 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]].

===Complete graphs===

[[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 on a circle, formingin a [[regular polygon]], with the remaining vertex at the center of the circle. 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''₂, ''K''₄, ''K''₆, ''K''₈, ... is 1, 1, 6, 6240, 1225566720, 252282619805368320, 98758655816833727741338583040, ... ({{oeis|A000438}}).

===1-factorization conjecture===

Line 26 ⟶ 28:

* 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;12n12''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_theoryGlossary 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

Line 52 ⟶ 73:

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

Line 75 ⟶ 96:

| issn = 0097-3165

| doi = 10.1006/jcta.2001.3240

| doi-access= free

}}

</ref>

Line 80 ⟶ 102:

==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 counterexamples[[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 graph]]sgraphs 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]].

==NotesReferences==

{{reflist}}

==ReferencesBibliography==

{{refbegin}}

*{{citation

|last1 = Bondy

|first1 = John Adrian

|authorlink1author-link1 = John Adrian Bondy

|last2 = Murty

|first2 = U. S. R.

|authorlink2author-link2 = U. S. R. Murty

|title = Graph Theory with Applications

|year = 1976

Line 121 ⟶ 143:

}}.

*{{citation

| last=Diestel | first=Reinhard | author-link = Reinhard Diestel

| title=Graph Theory

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

Line 129 ⟶ 151:

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

*{{citation

| last=Harary | first=Frank | authorlinkauthor-link=Frank Harary

| title=Graph Theory

| publisher=Addison-Wesley

Line 145 ⟶ 167:

| pages=117–125

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

| doi-access=

}}.

}}.

*{{citation

| last1=Perkovic | first1=L.

Line 155 ⟶ 178:

| pages=567–578

| doi=10.1016/S0012-365X(96)00202-6

| doi-access=

}}.

}}.

*{{citation

| last=Petersen | first=Julius | authorlinkauthor-link=Julius Petersen

| title=Die Theorie der regulären graphs

| journal=[[Acta Mathematica]]

Line 164 ⟶ 188:

| pages = 193–220

| doi = 10.1007/BF02392606| doi-access=free

| url=https://zenodo.org/record/2304433/files/article.pdf

}}.

*{{cite web

Line 170 ⟶ 195:

| title=1-Factorization Conjecture (1985?)

| work=Open Problems – Graph Theory and Combinatorics

| accessdateaccess-date=2010-01-09

| ref=West1FC

}}

Line 181 ⟶ 206:

{{refbegin}}

*{{citation

| last=Plummer | first=Michael D. | authorlinkauthor-link = Michael D. Plummer

| title=Graph factors and factorization: 1985–2003: A survey

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

Line 189 ⟶ 214:

| pages=791–821

| doi=10.1016/j.disc.2005.11.059

| doi-access=

}}.

}}.

{{refend}}

[[Category:Graph theory objects]]

[[Category:Factorization]]