Paper Info
Title
The Complexity of the Matching-cut Problem for Various Graph Classes
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 NP-complete for graphs with maximum degree 4, and gave a polynomial time algorithm for graphs with maximum degree 3.
Year
DOI
Venue
2003
10.1016/S1571-0653(04)00428-7
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
planar graph,maximum degree
Perfect graph,Discrete mathematics,Outerplanar graph,Combinatorics,Line graph,Graph property,Cubic graph,Factor-critical graph,Pathwidth,Maximum cut,Mathematics
Journal
Volume
ISSN
Citations 
13
1571-0653
0
PageRank 
References 
Authors
0.34
4
1
Name
Order
Citations
PageRank
Paul Bonsma128720.46