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 | M | = m and | N | = n , there is a perfect matching F in G such that M ⊆ F and N ∩ F = 0̸ . 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.