Matching Extension Missing Vertices and Edges in Triangulations of Surfaces

Research paper by Ken‐ichi Kawarabayashi, Kenta Ozeki, Michael D. Plummer

Indexed on: 14 Jun '16Published on: 01 May '16Published in: Journal of Graph Theory


Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let χ=χ(Σ) be the Euler characteristic of Σ. Suppose that V0⊆V(G) with |V(G)−V0| even and M and N are two matchings in G−V0 of sizes m and n respectively such that M∩N=∅. It is shown that if the pairwise distance between any two elements of V0∪M∪N is at least five and the face‐width of the embedding of G in Σ is at least max{20m−8χ−23,6}, then there is a perfect matching M0 in G−V0 containing M such that M0∩N=∅.