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

P.S. Bonsma

Research output: Contribution to journalArticleAcademic

37 Citations (Scopus)
3 Downloads (Pure)


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.
Original languageUndefined
Pages (from-to)109-126
JournalJournal of graph theory
Issue number2
Publication statusPublished - 2009


  • IR-72723
  • Planar graph
  • Matching-cut
  • Computational Complexity
  • decomposable graph

Cite this