Matching Cuts in Graphs of High Girth and H-Free Graphs

MaRDI QIDQ6421514zbMATH OpenFDO

Authors Carl Feghali, Felicia Lucke, Daniël Paulusma, Bernard Ries

Publication date 23 December 2022

Abstract: The (Perfect) Matching Cut problem is to decide if a connected graph has a (perfect) matching that is also an edge cut. The Disconnected Perfect Matching problem is to decide if a connected graph has a perfect matching that contains a matching cut. Both Matching Cut and Disconnected Perfect Matching are NP-complete for planar graphs of girth $5$, whereas Perfect Matching Cut is known to be NP-complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also NP-complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Our result for Matching Cut resolves a 20-year old open problem. We also show that the more general problem $d$-Cut, for every fixed $dgeq1$, is NP-complete for graphs of arbitrarily large fixed girth. Furthermore, we show that Matching Cut, Perfect Matching Cut and Disconnected Perfect Matching are NP-complete for $H$-free graphs whenever $H$ contains a connected component with two vertices of degree at least $3$. Afterwards, we update the state-of-the-art summaries for $H$-free graphs and compare them not only with each other, but also with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a given graph $G$. Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for $H$-subgraph-free graphs where $H$ is any finite set of graphs.

This page was built for publication: Matching Cuts in Graphs of High Girth and H-Free Graphs

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