The complexity of the matching-cut problem for planar graphs and other graph classes

The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Previously this problem was studied under the name of the Decomposable Graph Recognition problem, and proved to be -complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains -complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is -complete for planar graphs with girth five. The reduction is from planar graph 3-colorability and differs from earlier reductions. In addition, for certain graph classes polynomial time algorithms to find matching-cuts are described. These classes include claw-free graphs, co-graphs, and graphs with fixed bounded tree-width or clique-width.