×

Matching extension in toroidal quadrangulations. II: The 3-extendable case. (English) Zbl 1325.05133

Summary: A graph \(G\) containing a perfect matching is said to be \(m\)-extendable if \(m\leq(|V(G)|-2)/2\) and for every matching \(M\) with \(|M|=m\), there is a perfect matching \(F\) in \(G\) such that \(M\subseteq F\). R. E. L. Aldred et al. [ibid. 57, 217–233 (2013; Zbl 1293.05284)] characterized those quadrangulations of the torus which are 2-extendable. In the present work a characterization of those which are 3-extendable is obtained. Since no quadrangulation of the torus can be \(m\)-extendable for any \(m\geq 4\), this completes the study of \(m\)-extendability for toroidal quadrangulations. Moreover, by another previous result, it follows that we have therefore characterized all 3-extendable toroidal graphs.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)

Citations:

Zbl 1293.05284