A note on Matching-Cut in P_t-free Graphs

2021/11/23 by Feghali, Carl · 1 citation
#05C69 #Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2111.12011

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₅-free graphs, but that there exists an integer t > 0 for which it is NP-complete for P_t-free graphs.

Cited by

• Colouring Probe H-Free Graphs

Related

• Finding Matching Cuts in H-Free Graphs
• Finding Minimum Matching Cuts in H-free Graphs and Graphs of Bounded Radius and Diameter
• Finding d-Cuts in Claw-free Graphs
• Complexity and algorithms for matching cut problems in graphs without long induced paths and cycles
• Matching Cuts in Graphs of High Girth and H-Free Graphs