Extending matchings in graphs: A survey

AbstractGallai and Edmonds independently obtained a canonical decomposition of graphs in terms of their maximum matchings. Unfortunately, one of the degenerate cases for their theory occurs when the graph in question has a perfect matching (also known as a 1-factor). Kotzig, Lovász and others subsequently developed a further decomposition of such graphs. Among the ‘atoms’ of this decomposition is the family of bicritical graphs. (A graph G is bicritical if G - u - v has a perfect matching for every choice of two points u, v in G.) So far graphs have resisted further decomposition procedures.Motivated by these mysterious graphs, we introduced the following definition. Let p and n be positive integers with n </ (p − 2)/2. Graph G is n-extendable if G has a matching of size n and every such matching extends to (i.e. is a subset of) a perfect matching in G. It is clear that if a graph is bicritical, it is 1-extendable. A more interesting result is that if a graph is 2-extendable, it is either bipartite or bicritical. It is also true that if a graph is n-extendable, it is also (n − 1)-extendable. Hence, for nonbipartite graphs we have a nested sequence of families of bicritical graphs to study.In this paper, we survey a variety of results obtained over the past few years concerning n-extendable graphs. In particular, we describe how the property of n-extendability interacts with such other graph parameters as genus, toughness, claw-freedom and degree sums and generalized neighborhood conditions. We will also investigate the behavior of matching extendability under the operation of Cartesian product. The study of n-extendability for planar graphs has been, and continues to be, of particular interest