Extending matchings in graphs: A survey

DOI10.1016/0012-365X(92)00485-AzbMath0798.05040MaRDI QIDQ1322235

Michael D. Plummer

Publication date: 20 October 1994

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

decompositionplanar graphsmatchingsdegree sumsgenusbicritical graphstoughness\(n\)-extendable\(t\)-factorclaw-freedom

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to combinatorics (05-02) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items

Nice pairs of odd cycles in fullerene graphs ⋮ Characterizing \(2k\)-critical graphs and \(n\)-extendable graphs ⋮ On the \(p\)-factor-criticality of the Klein bottle ⋮ Matching extension in \(K_{1,r}\)-free graphs with independent claw centers ⋮ Hamiltonian extendable graphs ⋮ Matching extension and minimum degree ⋮ Generalization of matching extensions in graphs. IV: Closures ⋮ A characterization of maximal non-\(k\)-factor-critical graphs ⋮ Graph factors and factorization: 1985--2003: a survey ⋮ Toughness, binding number and restricted matching extension in a graph ⋮ 1-extendability of independent sets ⋮ Edge proximity and matching extension in punctured planar triangulations ⋮ Independence number in \(n\)-extendable graphs ⋮ Extendability and criticality in matching theory ⋮ Characterizing defect \(n\)-extendable bipartite graphs with different connectivities ⋮ Minimum size of \(n\)-factor-critical graphs and \(k\)-extendable graphs ⋮ On the extendability of quasi-strongly regular graphs with diameter 2 ⋮ Edge Proximity Conditions for Extendability in Planar Triangulations ⋮ Minimal graphs for 2-factor extension ⋮ Unnamed Item ⋮ Minimal graphs for matching extensions ⋮ The extendability of matchings in strongly regular graphs ⋮ Matching connectivity: on the structure of graphs with perfect matchings ⋮ \(M\)-alternating paths in \(n\)-extendable bipartite graphs ⋮ Matching extension and distance spectral radius ⋮ Matching extension and matching exclusion via the size or the spectral radius of graphs ⋮ The matcher game played in graphs ⋮ Equistarable Graphs and Counterexamples to Three Conjectures on Equistable Graphs ⋮ Unnamed Item ⋮ Subgraphs of Randomk-Edge-Colouredk-Regular Graphs ⋮ The classification of \(2\)-extendable edge-regular graphs with diameter \(2\) ⋮ The matching extension problem in general graphs is co-NP-complete ⋮ Matching extension in prism graphs ⋮ Max-cut and extendability of matchings in distance-regular graphs ⋮ The (\(n\), \(k\))-extendable graphs in surfaces ⋮ Characterizing minimally \(n\)-extendable bipartite graphs ⋮ Counting perfect matchings in \(n\)-extendable graphs ⋮ Algorithms for (0, 1,d)-graphs withdconstrains ⋮ Unnamed Item ⋮ Distance-restricted matching extension in planar triangulations ⋮ On the restricted matching extension of graphs in surfaces ⋮ Brace generation ⋮ 1-extendability of independent sets ⋮ Construction for bicritical graphs and \(k\)-extendable bipartite graphs ⋮ On some structural properties of generalized fullerene graphs with 13 pentagonal faces ⋮ On extendability of co-edge-regular graphs ⋮ A note on cyclic connectivity and matching properties of regular graphs ⋮ On matching extensions with prescribed and proscribed edge sets. II ⋮ Minimum degree of minimal defect \(n\)-extendable bipartite graphs ⋮ Plane elementary bipartite graphs ⋮ A local independence number condition for \(n\)-extendable graphs ⋮ Matchings and matching extensions in graphs ⋮ On extendability of Deza graphs with diameter 2 ⋮ Surface Embedding of Non-Bipartite $k$-Extendable Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The complexity of computing the permanent
• Extending matchings in planar graphs. IV
• Hamilton connected graphs
• Pfaffian orientations, 0-1 permanents, and even cycles in directed graphs
• The matching extendability of surfaces
• Brick decompositions and the matching rank of graphs
• Matching theory
• Matching extension and the genus of a graph
• Matching structure and the matching lattice
• Neighbourhood unions and Hamiltonian properties in graphs
• On maximal independent sets of vertices in claw-free graphs
• On n-extendable graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• On the 2-extendability of planar graphs
• The Cartesian product of a \(k\)-extendable and an \(l\)-extendable graph is \((k+l+1)\)-extendable
• Lower bound of cyclic edge connectivity for \(n\)-extendability of regular graphs
• Toughness and matching extension in graphs
• The statistics of dimers on a lattice
• A Theorem on Planar Graphs
• Note on Hamilton Circuits
• Toughness and the existence ofk-factors
• Cyclic coloration of 3-polytopes
• Rank of maximum matchings in a graph
• N‐extendability of symmetric graphs
• On the structure of factorizable graphs
• The Factorization of Linear Graphs
• A theorem on paths in planar graphs