Distance-restricted matching extension in planar triangulations

A graph G is said to have property E(m, n) if it contains a perfect matching and for every pair of disjoint matchings M and N in G with vertical bar M vertical bar = m and vertical bar N vertical bar = n, there is a perfect matching F in G such that M subset of F and N boolean AND F = phi. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m, n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3, 0), it was proved there that if the distance among the three edges is at least two, then they can always be extended to a perfect matching. In the present paper, we extend these results by considering the properties E(m, n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension. (c) 2010 Elsevier B.V. All rights reserved.