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

P.S. Bonsma

Research output: Contribution to journalArticleAcademic

19 Citations (Scopus)

Abstract

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
Volume62
Issue number2
DOIs
Publication statusPublished - 2009

Keywords

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

Cite this