2020/11/06 by Bouquet, Valentin, Picouleau, Christophe
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2011.03318
Perfect Matching-Cut is the problem of deciding whether a graph has a perfect matching that contains an edge-cut. We show that this problem is NP-complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five-regular graphs, for graphs of diameter three and for bipartite graphs of diameter four. We show that there exist polynomial time algorithms for the following classes of graphs: claw-free, P5-free, diameter two, bipartite with diameter three and graphs with bounded tree-width.