z-logo
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 = ∅ .

This content is not available in your region!

Continue researching here.

Having issues? You can contact us here
Accelerating Research

Address

John Eccles House
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom