Graph factorization: Difference between revisions

Revision as of 13:26, 14 February 2024

Revision as of 00:29, 7 March 2024

Line 1:

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

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 [[Cyclecycle (graph theory)|cyclescycle]]s that spans all vertices of the graph.

==1-factorization==

If a graph is 1-factorable (i.e., 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:

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

Line 36:

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:

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

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 [[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''&hairsp;+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]].

==References==