Premium
The complexity of the matching‐cut problem for planar graphs and other graph classes
Author(s) -
Bonsma Paul
Publication year - 2009
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20390
Subject(s) - combinatorics , mathematics , pathwidth , chordal graph , planar graph , 1 planar graph , discrete mathematics , book embedding , indifference graph , outerplanar graph , line graph , cograph , block graph , graph
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 ${\cal{NP}}$ ‐complete when restricted to graphs with maximum degree four. In this paper it is shown that the problem remains ${\cal{NP}}$ ‐complete for planar graphs with maximum degree four, answering a question by Patrignani and Pizzonia. It is also shown that the problem is ${\cal{NP}}$ ‐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. © 2009 Wiley Periodicals, Inc. J Graph Theory 62: 109–126, 2009