The matching extendability of surfaces
type: Item
instance of: scholarly article
title: The matching extendability of surfaces
zbMATH Open document ID: 0707.05051
DOI: 10.1016/0095-8956(92)90071-5
author: Nathaniel Dean
published in: Journal of Combinatorial Theory. Series B
publication date: 1991-01-01T00:00:00Z
review text: A connected graph G having at least \(2n+2\) vertices is said to be n- extendable if it contains a matching of size n and every such matching is contained in a perfect matching. M. D. Plummer posed the problem of determining the smallest integer \(\mu\) (\(\Sigma\)) such that no graph embeddable in the surface \(\Sigma\) is \(\mu\) (\(\Sigma\))-extendable. We call \(\mu\) (\(\Sigma\)) the matching extendability of \(\Sigma\) and show that if \(\Sigma\) is not homeomorphic to the sphere then \(\mu (\Sigma)=2+\lfloor \sqrt{4-2\chi}\rfloor\) where \(\chi\) is the Euler characteristic of \(\Sigma\). In particular, no projective planar graph is 3-extendable.
Mathematics Subject Classification ID: 05C70
zbMATH DE Number: 4160784
zbMATH Keywords: matching extendability
zbMATH Keywords: projective planar graph
MaRDI profile type: Publication
full work available at URL: 0095-8956(92)90071-5
OpenAlex ID: W2058404515
cites work: Q3880860
cites work: Q3097395
cites work: Extending subpermutation matrices in regular classes of matrices
cites work: Polytopes, graphs, and complexes
cites work: The Triangulation of Surfaces and the Heawood Color Formula
cites work: Q5678882
cites work: Q3784090
cites work: On n-extendable graphs
cites work: Q4732491
cites work: Matching extension and the genus of a graph
cites work: A theorem on paths in planar graphs
cites work: A Theorem on Planar Graphs
cites work: Q3847965
description: scientific article; zbMATH DE number 4160784