# On graph-transverse matchings

Given graphs $$G$$, $$H$$, is it possible to find a matching which, when deleted from $$G$$, destroys all copies of $$H$$? The answer is obvious for some inputs—notably, when $$G$$ is a large complete graph the answer is “no”—but in general this can be a very difficult question. In this thesis, we study this decision problem when $$H$$ is a fixed tree or cycle; our aim is to identify those $$H$$ for which it can be solved efficiently.

The $$H$$-transverse matching problem, $$\text{TM}(H)$$ for short, asks whether an input graph admits a matching $$M$$ such that no subgraph of $$G-M$$ is isomorphic to $$H$$. The main goal of this thesis is the following dichotomy. When $$H$$ is a triangle or one of a few small-diameter trees, there is a polynomial-time algorithm to find an $$H$$-transverse matching if one exists. However, $$\text{TM}(H)$$ is NP-complete when $$H$$ is any longer cycle or a tree of diameter ≥ 4. In addition, we study the restriction of these problems to structured graph classes.

On graph-transverse matchings. Ross Churchley. MSc thesis, University of Victoria. August 2012. (Senior supervisor: Jing Huang)