The complexity of the matching-cut probl
✍
Paul Bonsma
📂
Article
📅
2009
🏛
John Wiley and Sons
🌐
English
⚖ 247 KB
## 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 deg