Ross Churchley: Tree-transverse matchings and local consistency

A matching M in a graph G is called T-transverse if G-M does not contain T as a subgraph. These structures are relevant in graph Ramsey theory (when G is complete) and in the study of certain tilings (when G is planar), but for my master's research I focused on the algorithmic problem(s) of deciding whether a graph has such a matching.

For a fixed graph T, detecting T-transverse matchings is generally NP-complete, even when T is a (large-diameter) tree. However, efficient algorithms are available for a few small cases. The case where T=P_4, for instance, has at least two good solutions: a reduction to 2-SAT and a reduction to the perfect matching problem. The problem is also polynomial when T is the chair graph, and the cases where T is any other diameter-three tree are open.

This talk is a survey of the known algorithms for the P_4 and chair-transverse matching problems. It provides a common framework for these solutions which suggests characterizations for the existence of their respective matchings. This framework, known in the CSP literature as local consistency checking, is broadly applicable to other graph partition-type problems.