Some classes of graphs for which the property of having a perfect matching is preserved under certain vertex and/or edge deletions.
by
Richard Anstee
UBC, Vancouver, Canada

A few results are obtained which are `best possible' for the class of graphs under consideration. This is joint work with Aldred, Locke, and Tseng. We show that for the bipartite 2mx2m grid, if we delete an equal number of vertices of each part and in addition the vertices of each part are a constant times square root apart then the resulting graph has a perfect matching moreover if we change the constant, there are situations where the resulting graph no longer has a perfect matching. For edge deletion a mild condition on deleted edges is all that is needed. The problem of edge extendability is the same as deleting some edges and their endpoints. For the 2mx2m grid, as long as the set of edges to extend are mutually at distance at least 3 then the resulting graph has a perfect matching.

For a convex portion of the planar triangular tesselation, we show that vertex deletion, where the deleted vertices are at distance 3, results in a graph which either has a perfect matching or a near perfect matching.

Date received: April 9, 2008