A note on Matching-Cut in P_t-free Graphs
share
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.
READ FULL TEXT