Premium
Matching Extension Missing Vertices and Edges in Triangulations of Surfaces
Author(s) -
Kawarabayashi Kenichi,
Ozeki Kenta,
Plummer Michael D.
Publication year - 2017
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22058
Subject(s) - mathematics , combinatorics , euler characteristic , triangulation , embedding , matching (statistics) , extension (predicate logic) , surface (topology) , pairwise comparison , geometry , computer science , statistics , artificial intelligence , programming language
Let G be a 5‐connected triangulation of a surface Σ different from the sphere, and let χ = χ ( Σ ) be the Euler characteristic of Σ. Suppose thatV 0 ⊆ V ( G )with| V ( G ) − V 0 |even and M and N are two matchings in G − V 0of sizes m and n respectively such that M ∩ N = ∅ . It is shown that if the pairwise distance between any two elements ofV 0 ∪ M ∪ N is at least five and the face‐width of the embedding of G in Σ is at least max { 20 m − 8 χ − 23 , 6 } , then there is a perfect matching M 0 in G − V 0containing M such thatM 0 ∩ N = ∅ .