The matching extendability of surfaces
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.
scientific article; zbMATH DE number 4160784
scientific article