The Complexity of the Matching-cut Problem for Various Graph Classes

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. e NP-completeness results for the Matching-Cut problem for a few other graph classes, including planar graphs with maximum degree 4. Furthermore, we give polynomial time algorithms for the Matching-Cut problem for some graph classes.