Bounding the size of equimatchable graphs of fixed genus

DOI10.1007/S00373-008-0838-0MaRDI QIDQ1043800zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Michael D. Plummer

Publication date 9 December 2009

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00373-008-0838-0

zbMATH Keywords

equimatchable graphsGallai-Edmonds decomposition theoremmatchingminimal imbedding

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Review text

A graph \(G\) is equimatchable if every matching in \(G\) extends to a maximum matching in \(G\). In [Discrete Math. 266, No.1--3, 263--274 (2003; Zbl 1022.05065)], \textit{K.~Kawarabayashi}, \textit{M. D. Plummer} and \textit{A. Saito} showed that there are only a finite number of 3-connected equimatchable planar graphs. The present paper shows that in a surface (orientable or non-orientable) of any fixed genus there are only a finite number of 3-connected equimatchable graphs having a minimal imbedding of representativity at least three. (The latter hypothesis can be dropped, for non-bipartite graphs.) The proof uses the Gallai-Edmonds decomposition theorem for matchings.

Recommendations

• Equimatchable Graphs on Surfaces
• On two equimatchable graph classes
• Equimatchable regular graphs
• On three extensions of equimatchable graphs
• On two extensions of equimatchable graphs

Cites work

• Das Geschlecht des vollständigen paaren Graphen
• Der vollständige paare Graph auf nichtorientierbaren Flächen.
• Existence of polyhedral embeddings of graphs
• Graphs on surfaces
• scientific article; zbMATH DE number 3873377 (Why is no real title available?)
• scientific article; zbMATH DE number 4047749 (Why is no real title available?)
• scientific article; zbMATH DE number 3179262 (Why is no real title available?)
• scientific article; zbMATH DE number 16301 (Why is no real title available?)
• scientific article; zbMATH DE number 3220175 (Why is no real title available?)
• scientific article; zbMATH DE number 3232667 (Why is no real title available?)
• Matching theory
• Matching-perfect and cover-perfect graphs
• On n-extendable graphs
• On the matching extendability of graphs in surfaces
• On two equimatchable graph classes
• Paths, Trees, and Flowers
• Quelques consequences simples de la formule d'Euler
• Randomly matchable graphs
• SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEM
• Tilings of the Torus and the Klein Bottle and Vertex-Transitive Graphs on a Fixed Surface

Cited in

(9)

• Equimatchable claw-free graphs
• On two extensions of equimatchable graphs
• Efficient recognition of equimatchable graphs
• Edge-stable equimatchable graphs
• Equimatchable Graphs on Surfaces
• Equimatchable regular graphs
• Critical equimatchable graphs
• Equimatchable graphs are \(C_{2k+1}\)-free for \(k\geq 4\)
• Restricted matching in graphs of small genus

This page was built for publication: Bounding the size of equimatchable graphs of fixed genus

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1043800)