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)