A note on Matching-Cut in $P_t$-free Graphs

Abstract

A matching-cut of a graph is an edge cut that is a matching. The problem Matching-Cut is that of recognizing graphs with a matching-cut and is NP-complete, even if the graph belongs to one of a number of classes. We initiate the study of Matching-Cut for graphs without a fixed path as an induced subgraph. We show that Matching-Cut is in P for $P_5$-free graphs, but that there exists an integer $t>0$ for which it is NP-complete for $P_t$-free graphs.

7 pages, 3 figures; incorporated referees' suggestions

References in corpus (2)

• A complexity dichotomy for Matching Cut in (bipartite) graphs of fixed diameter
• A new characterization of $P_k$-free graphs