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

P.S. Bonsma

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

4 Citations (Scopus)

Abstract

The Matching-Cut problem is the problem to decide whether a graph has an edge cut that is also a matching. Chvátal studied this problem under the name of the Decomposable Graph Recognition problem, and proved the problem to be -complete for graphs with maximum degree 4, and gave a polynomial algorithm for graphs with maximum degree 3. In this paper it is shown that the problem is -complete when restricted to planar graphs with girth 5 and planar graphs with maximum degree 4. In addition, for claw-free graphs and planar graphs with girth at least 7 polynomial algorithms to find matching-cuts are described.
Original languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science
Subtitle of host publication29th International Workshop, WG 2003. Elspeet, The Netherlands, June 19-21, 2003. Revised Papers
EditorsHans L. Bodlaender
PublisherSpringer
Pages93-105
ISBN (Electronic)978-3-540-39890-5
ISBN (Print)978-3-540-20452-7
DOIs
Publication statusPublished - 2003
Event29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003 - Elspeet, Netherlands
Duration: 19 Jun 200321 Jun 2003
Conference number: 29

Publication series

NameLecture Notes in Computer Science
PublisherSpringer-Verlag
Volume2880
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Workshop

Workshop29th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2003
Abbreviated titleWG
CountryNetherlands
CityElspeet
Period19/06/0321/06/03

Keywords

  • IR-72724
  • METIS-214384

Fingerprint Dive into the research topics of 'The complexity of the matching-cut problem for planar graphs and other graph classes'. Together they form a unique fingerprint.

Cite this