Factor-critical graph: Difference between revisions

Content deleted Content added

Inline

Latest revision as of 04:50, 7 May 2024

In graph theory, a mathematical discipline, a factor-critical graph (or hypomatchable graph^[1]^[2]) is a graph with $n$ vertices in which every induced subgraph of $n - 1$ vertices has a perfect matching. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.)

A matching that covers all but one vertex of a graph is called a near-perfect matching. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.

Examples

Any odd-length cycle graph is factor-critical,^[1] as is any complete graph with an odd number of vertices.^[3] More generally, every Hamiltonian graph with an odd number of vertices is factor-critical. The friendship graphs (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but not Hamiltonian.

If a graph $G$ is factor-critical, then so is the Mycielskian of $G$ . For instance, the Grötzsch graph, the Mycielskian of a five-vertex cycle-graph, is factor-critical.^[4]

Every 2-vertex-connected claw-free graph with an odd number of vertices is factor-critical. For instance, the 11-vertex graph formed by removing a vertex from the regular icosahedron (the graph of the gyroelongated pentagonal pyramid) is both 2-connected and claw-free, so it is factor-critical. This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.^[5]

Characterizations

Factor-critical graphs may be characterized in several different ways, other than their definition as graphs in which each vertex deletion allows for a perfect matching:

Tibor Gallai proved that a graph is factor-critical if and only if it is connected and, for each node $v$ of the graph, there exists a maximum matching that does not include $v$ . It follows from these properties that the graph must have an odd number of vertices and that every maximum matching must match all but one vertex.^[6]
László Lovász proved that a graph is factor-critical if and only if it has an odd ear decomposition, a partition of its edges into a sequence of subgraphs, each of which is an odd-length path or cycle, with the first in the sequence being a cycle, each path in the sequence having both endpoints but no interior points on vertices in previous subgraphs, and each cycle other than the first in the sequence having exactly one vertex in previous subgraphs. For instance, the graph in the illustration may be partitioned in this way into a cycle of five edges and a path of three edges. In the case that a near-perfect matching of the factor-critical graph is also given, the ear decomposition can be chosen in such a way that each ear alternates between matched and unmatched edges.^[7]^[8]
A graph is also factor-critical if and only if it can be reduced to a single vertex by a sequence of contractions of odd-length cycles. Moreover, in this characterization, it is possible to choose each cycle in the sequence so that it contains the vertex formed by the contraction of the previous cycle.^[1] For instance, if one contracts the ears of an ear decomposition, in the order given by the decomposition, then at the time each ear is contracted it forms an odd cycle, so the ear decomposition characterization may be used to find a sequence of odd cycles to contract. Conversely from a sequence of odd cycle contractions, each containing the vertex formed from the previous contraction, one may form an ear decomposition in which the ears are the sets of edges contracted in each step.
Suppose that a graph $G$ is given together with a choice of a vertex $v$ and a matching $M$ that covers all vertices other than $v$ . Then $G$ is factor-critical if and only if there is a set of paths in $G$ , alternating between matched and unmatched edges, that connect $v$ to each of the other vertices in $G$ . Based on this property, it is possible to determine in linear time whether a graph $G$ with a given near-perfect matching is factor-critical.^[9]

Properties

Factor-critical graphs must always have an odd number of vertices, and must be 2-edge-connected (that is, they cannot have any bridges).^[10] However, they are not necessarily 2-vertex-connected; the friendship graphs provide a counterexample. It is not possible for a factor-critical graph to be bipartite, because in a bipartite graph with a near-perfect matching, the only vertices that can be deleted to produce a perfectly matchable graph are the ones on the larger side of the bipartition.

Every 2-vertex-connected factor-critical graph with $m$ edges has at least $m$ different near-perfect matchings, and more generally every factor-critical graph with $m$ edges and $c$ blocks (2-vertex-connected components) has at least $m - c + 1$ different near-perfect matchings. The graphs for which these bounds are tight may be characterized by having odd ear decompositions of a specific form.^[3]

Any connected graph may be transformed into a factor-critical graph by contracting sufficiently many of its edges. The minimal sets of edges that need to be contracted to make a given graph $G$ factor-critical form the bases of a matroid, a fact that implies that a greedy algorithm may be used to find the minimum weight set of edges to contract to make a graph factor-critical, in polynomial time.^[11]

Applications

A blossom is a factor-critical subgraph of a larger graph. Blossoms play a key role in Jack Edmonds' algorithms for maximum matching and minimum weight perfect matching in non-bipartite graphs.^[12]

In polyhedral combinatorics, factor-critical graphs play an important role in describing facets of the matching polytope of a given graph.^[1]^[2]

Generalizations and related concepts

A graph is said to be $k$ -factor-critical if every subset of $n - k$ vertices has a perfect matching. Under this definition, a hypomatchable graph is 1-factor-critical.^[13] Even more generally, a graph is $(a, b)$ -factor-critical if every subset of $n - k$ vertices has an $r$ -factor, that is, it is the vertex set of an $r$ -regular subgraph of the given graph.

A critical graph (without qualification) is usually assumed to mean a graph for which removing each of its vertices reduces the number of colors it needs in a graph coloring. The concept of criticality has been used much more generally in graph theory to refer to graphs for which removing each possible vertex changes or does not change some relevant property of the graph. A matching-critical graph is a graph for which the removal of any vertex does not change the size of a maximum matching; by Gallai's characterization, the matching-critical graphs are exactly the graphs in which every connected component is factor-critical.^[14] The complement graph of a critical graph is necessarily matching-critical, a fact that was used by Gallai to prove lower bounds on the number of vertices in a critical graph.^[15]

Beyond graph theory, the concept of factor-criticality has been extended to matroids by defining a type of ear decomposition on matroids and defining a matroid to be factor-critical if it has an ear decomposition in which all ears are odd.^[16]

References

^ ^a ^b ^c ^d Pulleyblank, W. R.; Edmonds, J. (1974), "Facets of 1-matching polyhedra", in Berge, C.; Ray-Chaudhuri, D. K. (eds.), Hypergraph Seminar, Lecture Notes in Mathematics, vol. 411, Springer-Verlag, pp. 214–242, doi:10.1007/BFb0066196, ISBN 978-3-540-06846-4.
^ ^a ^b Cornuéjols, G.; Pulleyblank, W. R. (1983), "Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem", Combinatorica, 3 (1): 35–52, doi:10.1007/BF02579340, MR 0716420, S2CID 35825797.
^ ^a ^b Liu, Yan; Hao, Jianxiu (2002), "The enumeration of near-perfect matchings of factor-critical graphs", Discrete Mathematics, 243 (1–3): 259–266, doi:10.1016/S0012-365X(01)00204-7, MR 1874747.
^ Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory, 25 (3): 261–266, doi:10.7151/dmgt.1279, MR 2232992.
^ Favaron, Odile; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Factor-criticality and matching extension in DCT-graphs", Discussiones Mathematicae Graph Theory, 17 (2): 271–278, CiteSeerX 10.1.1.25.6314, doi:10.7151/dmgt.1054, MR 1627955.
^ Gallai, T. (1963), "Neuer Beweis eines Tutte'schen Satzes", Magyar Tud. Akad. Mat. Kutató Int. Közl., 8: 135–139, MR 0166777. As cited by Frank, András; Szegő, László (2002), "Note on the path-matching formula" (PDF), Journal of Graph Theory, 41 (2): 110–119, CiteSeerX 10.1.1.20.7918, doi:10.1002/jgt.10055, MR 1926313, S2CID 206076722.
^ Lovász, L. (1972), "A note on factor-critical graphs", Studia Sci. Math. Hungar., 7: 279–280, MR 0335371.
^ Korte, Bernhard H.; Vygen, Jens (2008), "10.4 Ear-Decompositions of Factor-Critical Graphs", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21 (4th ed.), Springer-Verlag, pp. 235–241, ISBN 978-3-540-71843-7.
^ Lou, Dingjun; Rao, Dongning (2004), "Characterizing factor critical graphs and an algorithm" (PDF), The Australasian Journal of Combinatorics, 30: 51–56, MR 2080453.
^ Seyffarth, Karen (1993), "Packings and perfect path double covers of maximal planar graphs", Discrete Mathematics, 117 (1–3): 183–195, doi:10.1016/0012-365X(93)90334-P, MR 1226141.
^ Szigeti, Zoltán (1996), "On a matroid defined by ear-decompositions of graphs", Combinatorica, 16 (2): 233–241, doi:10.1007/BF01844849, MR 1401896, S2CID 206806006. For an earlier algorithm for contracting the minimum number of (unweighted) edges to reach a factor-critical graph, see Frank, András (1993), "Conservative weightings and ear-decompositions of graphs", Combinatorica, 13 (1): 65–81, doi:10.1007/BF01202790, MR 1221177, S2CID 10857300.
^ Edmonds, Jack (1965), "Paths, Trees and Flowers", Canadian Journal of Mathematics, 17: 449–467, doi:10.4153/CJM-1965-045-4, MR 0177907, S2CID 18909734.
^ Favaron, Odile (1996), "On $k$ -factor-critical graphs", Discussiones Mathematicae Graph Theory, 16 (1): 41–51, doi:10.7151/dmgt.1022, MR 1429805.
^ Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, doi:10.1006/jctb.1995.1026, MR 1328293.
^ Gallai, T. (1963b), "Kritische Graphen II", Publ. Math. Inst. Hungar. Acad. Sci., 8: 373–395. As cited by Stehlík, Matěj (2003), "Critical graphs with connected complements", Journal of Combinatorial Theory, Series B, 89 (2): 189–194, doi:10.1016/S0095-8956(03)00069-8, MR 2017723.
^ Szegedy, Balázs; Szegedy, Christian (2006), "Symplectic spaces and ear-decomposition of matroids", Combinatorica, 26 (3): 353–377, doi:10.1007/s00493-006-0020-3, MR 2246153, S2CID 11578490.

[pe74-1] Pulleyblank, W. R.; Edmonds, J. (1974), "Facets of 1-matching polyhedra", in Berge, C.; Ray-Chaudhuri, D. K. (eds.), Hypergraph Seminar, Lecture Notes in Mathematics, vol. 411, Springer-Verlag, pp. 214–242, doi:10.1007/BFb0066196, ISBN 978-3-540-06846-4.

[cp83-2] Cornuéjols, G.; Pulleyblank, W. R. (1983), "Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem", Combinatorica, 3 (1): 35–52, doi:10.1007/BF02579340, MR 0716420, S2CID 35825797.

[lh02-3] Liu, Yan; Hao, Jianxiu (2002), "The enumeration of near-perfect matchings of factor-critical graphs", Discrete Mathematics, 243 (1–3): 259–266, doi:10.1016/S0012-365X(01)00204-7, MR 1874747.

[4] Došlić, Tomislav (2005), "Mycielskians and matchings", Discussiones Mathematicae Graph Theory, 25 (3): 261–266, doi:10.7151/dmgt.1279, MR 2232992.

[5] Favaron, Odile; Flandrin, Evelyne; Ryjáček, Zdeněk (1997), "Factor-criticality and matching extension in DCT-graphs", Discussiones Mathematicae Graph Theory, 17 (2): 271–278, CiteSeerX 10.1.1.25.6314, doi:10.7151/dmgt.1054, MR 1627955.

[6] Gallai, T. (1963), "Neuer Beweis eines Tutte'schen Satzes", Magyar Tud. Akad. Mat. Kutató Int. Közl., 8: 135–139, MR 0166777. As cited by Frank, András; Szegő, László (2002), "Note on the path-matching formula" (PDF), Journal of Graph Theory, 41 (2): 110–119, CiteSeerX 10.1.1.20.7918, doi:10.1002/jgt.10055, MR 1926313, S2CID 206076722.

[7] Lovász, L. (1972), "A note on factor-critical graphs", Studia Sci. Math. Hungar., 7: 279–280, MR 0335371.

[8] Korte, Bernhard H.; Vygen, Jens (2008), "10.4 Ear-Decompositions of Factor-Critical Graphs", Combinatorial Optimization: Theory and Algorithms, Algorithms and Combinatorics, vol. 21 (4th ed.), Springer-Verlag, pp. 235–241, ISBN 978-3-540-71843-7.

[9] Lou, Dingjun; Rao, Dongning (2004), "Characterizing factor critical graphs and an algorithm" (PDF), The Australasian Journal of Combinatorics, 30: 51–56, MR 2080453.

[10] Seyffarth, Karen (1993), "Packings and perfect path double covers of maximal planar graphs", Discrete Mathematics, 117 (1–3): 183–195, doi:10.1016/0012-365X(93)90334-P, MR 1226141.

[11] Szigeti, Zoltán (1996), "On a matroid defined by ear-decompositions of graphs", Combinatorica, 16 (2): 233–241, doi:10.1007/BF01844849, MR 1401896, S2CID 206806006. For an earlier algorithm for contracting the minimum number of (unweighted) edges to reach a factor-critical graph, see Frank, András (1993), "Conservative weightings and ear-decompositions of graphs", Combinatorica, 13 (1): 65–81, doi:10.1007/BF01202790, MR 1221177, S2CID 10857300.

[12] Edmonds, Jack (1965), "Paths, Trees and Flowers", Canadian Journal of Mathematics, 17: 449–467, doi:10.4153/CJM-1965-045-4, MR 0177907, S2CID 18909734.

[13] Favaron, Odile (1996), "On $k$ -factor-critical graphs", Discussiones Mathematicae Graph Theory, 16 (1): 41–51, doi:10.7151/dmgt.1022, MR 1429805.

[14] Erdős, P.; Füredi, Z.; Gould, R. J.; Gunderson, D. S. (1995), "Extremal graphs for intersecting triangles", Journal of Combinatorial Theory, Series B, 64 (1): 89–100, doi:10.1006/jctb.1995.1026, MR 1328293.

[15] Gallai, T. (1963b), "Kritische Graphen II", Publ. Math. Inst. Hungar. Acad. Sci., 8: 373–395. As cited by Stehlík, Matěj (2003), "Critical graphs with connected complements", Journal of Combinatorial Theory, Series B, 89 (2): 189–194, doi:10.1016/S0095-8956(03)00069-8, MR 2017723.

[16] Szegedy, Balázs; Szegedy, Christian (2006), "Symplectic spaces and ear-decomposition of matroids", Combinatorica, 26 (3): 353–377, doi:10.1007/s00493-006-0020-3, MR 2246153, S2CID 11578490.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

@@ Line 1: / Line 1: @@
-[[Image:Factor critical.svg|thumb|300px|A factor-critical graph, together with [[perfect matching]]s of the subgraphs formed by removing one of its vertices.]]
+{{Short description|Graph of n vertices with a perfect matching for every subgraph of n-1 vertices}}
+[[File:Factor critical.svg|thumb|300px|A factor-critical graph, together with [[perfect matching]]s of the subgraphs formed by removing one of its vertices.]]
-In [[graph theory]], a mathematical discipline, a '''factor-critical graph''' is a [[graph (mathematics)|graph]] with {{mvar|n}} vertices in which any subset of {{math|''n'' &minus; 1}} vertices has a [[perfect matching]]. Factor-critical graphs are also called '''hypomatchable graphs'''.<ref name="pe74"/><ref name="cp83">{{citation
+In [[graph theory]], a mathematical discipline, a '''factor-critical graph''' (or '''hypomatchable graph'''<ref name="pe74"/><ref name="cp83">{{citation
- | last1 = Cornuéjols | first1 = G.
+ | last1 = Cornuéjols | first1 = G. | author1-link = Gérard Cornuéjols
- | last2 = Pulleyblank | first2 = W. R.
+ | last2 = Pulleyblank | first2 = W. R. | author2-link = William R. Pulleyblank
  | doi = 10.1007/BF02579340
  | issue = 1
- | journal = Combinatorica
+ | journal = [[Combinatorica]]
  | mr = 716420
  | pages = 35–52
  | title = Critical graphs, matchings and tours or a hierarchy of relaxations for the travelling salesman problem
  | volume = 3
+ | year = 1983| s2cid = 35825797 }}.</ref>) is a [[Graph (discrete mathematics)|graph]] with {{mvar|n}} vertices in which every induced subgraph of {{math|''n'' &minus; 1}} vertices has a [[perfect matching]]. (A perfect matching in a graph is a subset of its edges with the property that each of its vertices is the endpoint of exactly one of the edges in the subset.)
- | year = 1983}}.</ref>
+A matching that covers all but one vertex of a graph is called a '''near-perfect matching'''. So equivalently, a factor-critical graph is a graph in which there are near-perfect matchings that avoid every possible vertex.
 ==Examples==
-[[File:Friendship graphs.svg|thumb|240px|Three [[friendship graph]]s, examples of non-Hamiltonian factor-critical graphs.]]
+[[File:Friendship graphs.svg|thumb|240px|Three [[friendship graph]]s, examples of non-Hamiltonian factor-critical graphs]]
-Any odd-length [[cycle graph]] is factor-critical,<ref name="pe74"/> as is any [[complete graph]] with an odd number of vertices.<ref name="lh02"/> More generally, every [[Hamiltonian cycle|Hamiltonian]] graph with an odd number of vertices is factor-critical. The [[friendship graph]]s provide examples of graphs that are factor-critical but not Hamiltonian.
+[[File:Gyroelongated pentagonal pyramid.png|thumb|The [[gyroelongated pentagonal pyramid]], a [[claw-free graph|claw-free]] factor-critical graph]]
+Any odd-length [[cycle graph]] is factor-critical,<ref name="pe74"/> as is any [[complete graph]] with an odd number of vertices.<ref name="lh02"/> More generally, every [[Hamiltonian cycle|Hamiltonian]] graph with an odd number of vertices is factor-critical. The [[friendship graph]]s (graphs formed by connecting a collection of triangles at a single common vertex) provide examples of graphs that are factor-critical but not Hamiltonian.
 If a graph {{mvar|G}} is factor-critical, then so is the [[Mycielskian]] of {{mvar|G}}. For instance, the [[Grötzsch graph]], the Mycielskian of a five-vertex cycle-graph, is factor-critical.<ref>{{citation
  | last = Došlić | first = Tomislav
  | issue = 3
- | journal = Discussiones Mathematicae. Graph Theory
+ | journal = Discussiones Mathematicae Graph Theory
  | mr = 2232992
  | pages = 261–266
  | title = Mycielskians and matchings
+ | url = http://www.discuss.wmie.uz.zgora.pl/php/discuss.php?ip=&url=pdf&nIdA=14414&nIdSesji=-1
  | volume = 25
- | year = 2005}}.</ref>
+ | year = 2005
+ | doi=10.7151/dmgt.1279| doi-access = free
+ }}.</ref>
+Every [[k-vertex-connected graph|2-vertex-connected]] [[claw-free graph]] with an odd number of vertices is factor-critical. For instance, the 11-vertex graph formed by removing a vertex from the [[regular icosahedron]] (the graph of the [[gyroelongated pentagonal pyramid]]) is both 2-connected and claw-free, so it is factor-critical. This result follows directly from the more fundamental theorem that every connected claw-free graph with an even number of vertices has a perfect matching.<ref>{{citation
+ | last1 = Favaron | first1 = Odile | author1-link = Odile Favaron
+ | last2 = Flandrin | first2 = Evelyne
+ | last3 = Ryjáček | first3 = Zdeněk
+ | issue = 2
+ | journal = Discussiones Mathematicae Graph Theory
+ | mr = 1627955
+ | pages = 271–278
+ | title = Factor-criticality and matching extension in DCT-graphs
+ | url = http://www.discuss.wmie.uz.zgora.pl/php/discuss.php?ip=&url=pdf&nIdA=3481&nIdSesji=-1
+ | volume = 17
+ | year = 1997 | doi=10.7151/dmgt.1054| citeseerx = 10.1.1.25.6314
+ }}.</ref>
 ==Characterizations==
@@ Line 40: / Line 61: @@
  | doi = 10.1002/jgt.10055
  | issue = 2
- | journal = Journal of Graph Theory
+ | journal = [[Journal of Graph Theory]]
  | mr = 1926313
  | pages = 110–119
@@ Line 46: / Line 67: @@
  | url = http://www.cs.elte.hu/~frank/cikkek/FrankJ43.PDF
  | volume = 41
- | year = 2002}}.</ref>
+ | year = 2002| citeseerx = 10.1.1.20.7918 | s2cid = 206076722 }}.</ref>
 *[[László Lovász]] proved that a graph is factor-critical if and only if it has an odd [[ear decomposition]], a partition of its edges into a sequence of subgraphs, each of which is an odd-length [[path (graph theory)|path]] or [[cycle (graph theory)|cycle]], with the first in the sequence being a cycle, each path in the sequence having both endpoints but no interior points on vertices in previous subgraphs, and each cycle other than the first in the sequence having exactly one vertex in previous subgraphs. For instance, the graph in the illustration may be partitioned in this way into a cycle of five edges and a path of three edges. In the case that a near-perfect matching of the factor-critical graph is also given, the ear decomposition can be chosen in such a way that each ear alternates between matched and unmatched edges.<ref>
-{{citation|first=L.|last=Lovász|authorlink=László Lovász|title=A note on factor-critical graphs|journal=Studia Sci. Math. Hungar.|volume=7|year=1972|pages=279–280|mr=0335371}}.</ref><ref>{{citation|title=Combinatorial Optimization: Theory and Algorithms|volume=21|series=Algorithms and Combinatorics|first1=Bernhard H.|last1=Korte|first2=Jens|last2=Vygen|edition=4th|publisher=Springer-Verlag|year=2008|isbn=9783540718437|contribution=10.4 Ear-Decompositions of Factor-Critical Graphs|url=http://books.google.com/books?id=UnYwgPltSjwC&pg=PA235|pages=235–241}}.</ref>
+{{citation|first=L.|last=Lovász|authorlink=László Lovász|title=A note on factor-critical graphs|journal=Studia Sci. Math. Hungar.|volume=7|year=1972|pages=279–280|mr=0335371}}.</ref><ref>{{citation|title=Combinatorial Optimization: Theory and Algorithms|volume=21|series=Algorithms and Combinatorics|first1=Bernhard H.|last1=Korte|author1-link = Bernhard Korte|first2=Jens|last2=Vygen|edition=4th|publisher=Springer-Verlag|year=2008|isbn=978-3-540-71843-7|contribution=10.4 Ear-Decompositions of Factor-Critical Graphs|url=https://books.google.com/books?id=UnYwgPltSjwC&pg=PA235|pages=235–241}}.</ref>
-*A graph is also factor-critical if and only if it can be reduced to a single graph by a sequence of [[edge contraction|contractions]] of odd-length cycles. Moreover, in this characterization, it is possible to choose each cycle in the sequence so that it contains the vertex formed by the contraction of the previous cycle.<ref name="pe74">{{citation
+*A graph is also factor-critical if and only if it can be reduced to a single vertex by a sequence of [[edge contraction|contractions]] of odd-length cycles. Moreover, in this characterization, it is possible to choose each cycle in the sequence so that it contains the vertex formed by the contraction of the previous cycle.<ref name="pe74">{{citation
- | last1 = Pulleyblank | first1 = W. R.
+ | last1 = Pulleyblank | first1 = W. R. | author1-link = William R. Pulleyblank
  | last2 = Edmonds | first2 = J. | author2-link = Jack Edmonds
- | editor1-last = Berge | editor1-first = C.
+ | editor1-last = Berge | editor1-first = C. | editor1-link = Claude Berge
- | editor2-last = Ray-Chaudhuri | editor2-first = D. K.
+ | editor2-last = Ray-Chaudhuri | editor2-first = D. K. | editor2-link = Dwijendra Kumar Ray-Chaudhuri
  | contribution = Facets of 1-matching polyhedra
  | doi = 10.1007/BFb0066196
@@ Line 61: / Line 82: @@
  | title = Hypergraph Seminar
  | volume = 411
+ | year = 1974
- | year = 1974}}.</ref> For instance, if one contracts the ears of an ear decomposition, in the order given by the decomposition, then at the time each ear is contracted it forms an odd cycle, so the ear decomposition characterization may be used to find a sequence of odd cycles to contract. Conversely from a sequence of odd cycle contractions, each containing the vertex formed from the previous contraction, one may form an ear decomposition in which the ears are the sets of edges contracted in each step.
+ | isbn = 978-3-540-06846-4}}.</ref> For instance, if one contracts the ears of an ear decomposition, in the order given by the decomposition, then at the time each ear is contracted it forms an odd cycle, so the ear decomposition characterization may be used to find a sequence of odd cycles to contract. Conversely from a sequence of odd cycle contractions, each containing the vertex formed from the previous contraction, one may form an ear decomposition in which the ears are the sets of edges contracted in each step.
 *Suppose that a graph {{mvar|G}} is given together with a choice of a vertex {{mvar|v}} and a matching {{mvar|M}} that covers all vertices other than {{mvar|v}}. Then {{mvar|G}} is factor-critical if and only if there is a set of paths in {{mvar|G}}, alternating between matched and unmatched edges, that connect {{mvar|v}} to each of the other vertices in {{mvar|G}}. Based on this property, it is possible to determine in [[linear time]] whether a graph {{mvar|G}} with a given near-perfect matching is factor-critical.<ref>{{citation
  | last1 = Lou | first1 = Dingjun
@@ Line 77: / Line 99: @@
  | last = Seyffarth | first = Karen
  | doi = 10.1016/0012-365X(93)90334-P
- | issue = 1-3
+ | issue = 1–3
- | journal = Discrete Mathematics
+ | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
  | mr = 1226141
  | pages = 183–195
  | title = Packings and perfect path double covers of maximal planar graphs
  | volume = 117
+ | year = 1993| doi-access = free
- | year = 1993}}.</ref> However, they are not necessarily [[k-vertex-connected graph|2-vertex-connected]]; the friendship graphs provide a counterexample. It is not possible for a factor-critical graph to be [[bipartite graph|bipartite]], because in a bipartite graph with a near-perfect matching, the only vertices that can be deleted to produce a perfectly matchable graph are the ones on the larger side of the bipartition.
+ }}.</ref> However, they are not necessarily [[k-vertex-connected graph|2-vertex-connected]]; the friendship graphs provide a counterexample. It is not possible for a factor-critical graph to be [[bipartite graph|bipartite]], because in a bipartite graph with a near-perfect matching, the only vertices that can be deleted to produce a perfectly matchable graph are the ones on the larger side of the bipartition.
 Every 2-vertex-connected factor-critical graph with {{mvar|m}} edges has at least {{mvar|m}} different near-perfect matchings, and more generally every factor-critical graph with {{mvar|m}} edges and {{mvar|c}} blocks (2-vertex-connected components) has at least {{math|''m'' &minus; ''c'' + 1}} different near-perfect matchings. The graphs for which these bounds are tight may be characterized by having odd ear decompositions of a specific form.<ref name="lh02">{{citation
@@ Line 89: / Line 112: @@
  | last2 = Hao | first2 = Jianxiu
  | doi = 10.1016/S0012-365X(01)00204-7
- | issue = 1-3
+ | issue = 1–3
- | journal = Discrete Mathematics
+ | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
  | mr = 1874747
  | pages = 259–266
  | title = The enumeration of near-perfect matchings of factor-critical graphs
  | volume = 243
- | year = 2002}}.</ref>
+ | year = 2002| doi-access =
+ }}.</ref>
 Any connected graph may be transformed into a factor-critical graph by  [[edge contraction|contracting]] sufficiently many of its edges. The [[minimal element|minimal]] sets of edges that need to be contracted to make a given graph {{mvar|G}} factor-critical form the bases of a [[matroid]], a fact that implies that a [[greedy algorithm]] may be used to find the minimum weight set of edges to contract to make a graph factor-critical, in [[polynomial time]].<ref>{{citation
@@ Line 101: / Line 125: @@
  | doi = 10.1007/BF01844849
  | issue = 2
- | journal = Combinatorica
+ | journal = [[Combinatorica]]
  | mr = 1401896
  | pages = 233–241
  | title = On a matroid defined by ear-decompositions of graphs
  | volume = 16
- | year = 1996}}. For an earlier algorithm for contracting the minimum number of (unweighted) edges to reach a factor-critical graph, see {{citation
+ | year = 1996| s2cid = 206806006
+ }}. For an earlier algorithm for contracting the minimum number of (unweighted) edges to reach a factor-critical graph, see {{citation
  | last = Frank | first = András | author-link = András Frank
  | doi = 10.1007/BF01202790
  | issue = 1
- | journal = Combinatorica
+ | journal = [[Combinatorica]]
  | mr = 1221177
  | pages = 65–81
  | title = Conservative weightings and ear-decompositions of graphs
  | volume = 13
- | year = 1993}}.</ref>
+ | year = 1993| s2cid = 10857300 }}.</ref>
 ==Applications==
-A '''blossom''' is  a factor-critical [[subgraph]] of a larger graph. Blossoms play a key role in [[Jack Edmonds]]' [[Edmonds's_matching_algorithm|algorithm]]s for [[maximum matching]] and minimum weight perfect matching in non-bipartite graphs.<ref>{{citation | author=Edmonds, Jack | authorlink = Jack Edmonds | title=Paths, Trees and Flowers | journal=Canadian Journal of Mathematics | volume=17 | year=1965 | pages=449–467 | mr = 0177907 | doi=10.4153/CJM-1965-045-4}}.</ref>
+A '''blossom''' is  a factor-critical [[Glossary of graph theory#Subgraphs|subgraph]] of a larger graph. Blossoms play a key role in [[Jack Edmonds]]' [[Edmonds's_matching_algorithm|algorithm]]s for [[maximum matching]] and minimum weight perfect matching in non-bipartite graphs.<ref>{{citation | author=Edmonds, Jack | authorlink = Jack Edmonds | title=Paths, Trees and Flowers | journal=[[Canadian Journal of Mathematics]] | volume=17 | year=1965 | pages=449–467 | mr = 0177907 | doi=10.4153/CJM-1965-045-4| s2cid = 18909734 | doi-access=free }}.</ref>
 In [[polyhedral combinatorics]], factor-critical graphs play an important role in describing facets of the [[matching polytope]] of a given graph.<ref name="pe74"/><ref name="cp83"/>
@@ Line 124: / Line 149: @@
 ==Generalizations and related concepts==
 A graph is said to be {{mvar|k}}-factor-critical if every subset of {{math|''n'' &minus; ''k''}} vertices has a perfect matching. Under this definition, a hypomatchable graph is 1-factor-critical.<ref>{{citation
- | last = Favaron | first = Odile
+ | last = Favaron | first = Odile | authorlink = Odile Favaron
  | issue = 1
- | journal = Discussiones Mathematicae. Graph Theory
+ | journal = Discussiones Mathematicae Graph Theory
  | mr = 1429805
  | pages = 41–51
  | title = On {{mvar|k}}-factor-critical graphs
+ | url = http://www.discuss.wmie.uz.zgora.pl/php/discuss.php?ip=&url=pdf&nIdA=3543&nIdSesji=-1
  | volume = 16
+ | year = 1996
- | year = 1996}}.</ref> Even more generally, a graph is {{math|(''a'',''b'')}}-factor-critical if every subset of {{math|''n'' &minus; ''k''}} vertices has an {{mvar|r}}-factor, that is, it is the vertex set of an [[regular graph|{{mvar|r}}-regular subgraph]] of the given graph.
+ | doi=10.7151/dmgt.1022| doi-access = free
+ }}.</ref> Even more generally, a graph is {{math|(''a'',''b'')}}-factor-critical if every subset of {{math|''n'' &minus; ''k''}} vertices has an {{mvar|r}}-factor, that is, it is the vertex set of an [[regular graph|{{mvar|r}}-regular subgraph]] of the given graph.
-A [[critical graph]] (without qualification) is usually assumed to mean a graph for which removing each of its vertices reduces the number of colors it needs in a [[graph coloring]], but the concept of criticality has been used much more generally in graph theory to refer to graphs for which removing each possible vertex changes some relevant property of the graph.
+A [[critical graph]] (without qualification) is usually assumed to mean a graph for which removing each of its vertices reduces the number of colors it needs in a [[graph coloring]]. The concept of criticality has been used much more generally in graph theory to refer to graphs for which removing each possible vertex changes or does not change some relevant property of the graph. A '''matching-critical graph''' is a graph for which the removal of any vertex does not change the size of a [[maximum matching]]; by Gallai's characterization, the matching-critical graphs are exactly the graphs in which every connected component is factor-critical.<ref>{{citation
+ | last1 = Erdős | first1 = P. | author1-link = Paul Erdős
+ | last2 = Füredi | first2 = Z. | author2-link = Zoltán Füredi
+ | last3 = Gould | first3 = R. J. | author3-link = Ronald J. Gould
+ | last4 = Gunderson | first4 = D. S.
+ | doi = 10.1006/jctb.1995.1026
+ | issue = 1
+ | journal = [[Journal of Combinatorial Theory]]
+ | mr = 1328293
+ | pages = 89–100
+ | series = Series B
+ | title = Extremal graphs for intersecting triangles
+ | url = http://www.math.uiuc.edu/~z-furedi/PUBS/furedi_erdos_gould_gunderson_triangles.ps
+ | volume = 64
+ | year = 1995| doi-access = free
+ }}.</ref> The [[complement graph]] of a critical graph is necessarily matching-critical, a fact that was used by Gallai to prove lower bounds on the number of vertices in a critical graph.<ref>{{citation
+ | last = Gallai | first = T. | author-link = Tibor Gallai
+ | journal = Publ. Math. Inst. Hungar. Acad. Sci.
+ | pages = 373–395
+ | title = Kritische Graphen II
+ | volume = 8
+ | year = 1963b}}. As cited by {{citation
+ | last = Stehlík | first = Matěj
+ | doi = 10.1016/S0095-8956(03)00069-8
+ | issue = 2
+ | journal = [[Journal of Combinatorial Theory]]
+ | mr = 2017723
+ | pages = 189–194
+ | series = Series B
+ | title = Critical graphs with connected complements
+ | volume = 89
+ | year = 2003| doi-access =
+ }}.</ref>
 Beyond graph theory, the concept of factor-criticality has been extended to [[matroid]]s by defining a type of ear decomposition on matroids and defining a matroid to be factor-critical if it has an ear decomposition in which all ears are odd.<ref>{{citation
- | last1 = Szegedy | first1 = Balázs
+ | last1 = Szegedy | first1 = Balázs | author1-link = Balázs Szegedy
  | last2 = Szegedy | first2 = Christian
  | doi = 10.1007/s00493-006-0020-3
  | issue = 3
- | journal = Combinatorica. An International Journal on Combinatorics and the Theory of Computing
+ | journal = [[Combinatorica]]
  | mr = 2246153
  | pages = 353–377
  | title = Symplectic spaces and ear-decomposition of matroids
  | volume = 26
- | year = 2006}}.</ref>
+ | year = 2006| s2cid = 11578490 }}.</ref>
 == References ==
@@ Line 151: / Line 211: @@
 [[Category:Graph families]]
-[[Category:Matching]]
+[[Category:Matching (graph theory)]]