Matching cut and variants in graphs of bounded radius, bounded diameter and h-free graphs

Abstract

A matching in a graph G = (V, E) is a set M ⊆ E, such that no two edges in M share an endvertex. An edge cut in G is a set of edges C ⊆ E, such that we can partition V into two non-empty sets R and B, where C is the set of edges with one endvertex in R and one in B. A matching cut is a set of edges M ⊆ E which is both a matching and an edge cut. In this thesis, we consider the decision problems Matching Cut, its variants Disconnected Perfect Matching and Perfect Matching Cut, as well as its generalisation d-Cut. We give polynomial time algorithms and NP-completeness results for certain graph classes, including H-free graphs, for some graphs H, and graphs of bounded radius and diameter. In particular, we solve a 20-year old open problem by showing the NP-completeness of Matching Cut for graphs of high girth. We also consider the maximisation version Maximum Matching Cut, where we ask for a matching cut of maximum size, that is with the maximum number of edges in the matching cut. For this variant we give a complexity dichotomy for graphs of bounded radius, bounded diameter, H-free graphs and bipartite graphs of bounded radius and diameter. We conclude with a comparison of all variants, which allows to identify interesting open problems.