Paper Info
Title
The complexity of the matching-cut problem for planar graphs and other graph classes
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 ${\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 A preliminary version of this paper appeared in the proceedings of WG 2003, LNCS 2880.
Year
DOI
Venue
2009
10.1002/jgt.v62:2
Journal of Graph Theory
Keywords
Field
DocType
matching,decomposable graph,computational complexity.,planar graph,edge cut,computational complexity,maximum degree,bipartite graph,claw free graph
Discrete mathematics,Odd graph,Combinatorics,Outerplanar graph,Indifference graph,Chordal graph,Bipartite graph,Cograph,Pathwidth,1-planar graph,Mathematics
Journal
Volume
Issue
ISSN
62
2
0364-9024
Citations 
PageRank 
References 
7
0.75
12
Authors
1
Name
Order
Citations
PageRank
Paul Bonsma128720.46