Distance-restricted matching extension in planar triangulations

A graph GG is said to have property E(m,n)E(m,n) if it contains a perfect matching and for every pair of disjoint matchings MM and NN in GG with |M|=m|M|=m and |N|=n|N|=n, there is a perfect matching FF in GG such that M⊆FM⊆F and N∩F=0̸N∩F=0̸. In a previous paper (Aldred and Plummer 2001) [2], an investigation of the property E(m,n)E(m,n) was begun for graphs embedded in the plane. In particular, although no planar graph is E(3,0)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)E(m,n) for planar triangulations when more general distance restrictions are imposed on the edges to be included and avoided in the extension.