A note on Matching-Cut in P_t-free Graphs

DOI10.1016/J.IPL.2022.106294MaRDI QIDQ6383772arXivFDO

Authors Carl Feghali

Publication date 23 November 2021

Published in arXiv

Full work available at URL https://doi.org/10.1016/J.IPL.2022.106294

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

arXiv classification

cs.DMcs.DSmath.CO

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.

This page was built for publication: A note on Matching-Cut in $P_t$-free Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6383772)