Proximity thresholds for matching extension in planar and projective planar triangulations
A graph on at least 2(m + 1) vertices with a perfect matching is said to be m-extendable if, given any matching M with |M| = m, there is a perfect matching F in G such that M?F. It has been known for some time that no planar graph is 3-extendable. More recently, a graph on at least 2m+ 2 vertices has been defined to be distance d m-extendable if given any matching M with |M| = min which the edges lie at pair-wise distance at least d, there is a perfect matching containing M.
projective planar triangulation planar triangulation distance restricted matching extension