Premium
Distance restricted matching extension missing vertices and edges in 5‐connected triangulations of the plane
Author(s) -
Aldred R. E. L.,
Plummer Michael D.,
Ruksasakchai Watcharintorn
Publication year - 2020
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.22560
Subject(s) - mathematics , combinatorics , triangulation , matching (statistics) , euler characteristic , embedding , extension (predicate logic) , planar , geometry , computer science , artificial intelligence , statistics , computer graphics (images) , programming language
In [4] it was shown that in a 5‐connected even planar triangulation G , every matching M of size | M | < | V ( G ) | / 2can be extended to a perfect matching of G , as long as the edges of M lie at distance at least 5 from each other. Somewhat later in [7], the following result was proved. Let G be a 5‐connected triangulation of a surface Σ different from the sphere . Let χ = χ ( Σ ) be the Euler characteristic of Σ . Suppose V 0 ⊂ V ( G ) with | V ( G ) − V 0 | even and M and N are two matchings in G − V 0 such that M ∩ N = ∅ . Further suppose that the pairwise distance between two elements of V 0 ∪ M ∪ N is at least 5 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 0 which contains M such that M 0 ∩ N = ∅ . In the present paper, we present some results which, in a sense, lie in the gap between the two above theorems, in that they deal with restricted matching extension in a planar triangulation when a set of vertices which lie pairwise at sufficient distance from one another has been deleted. In particular, we prove a planar analogue of the result in [7] stated above.