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

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 -complete for planar graphs of girth 5, whereas Perfect Matching Cut is known to be -complete even for subcubic bipartite graphs of arbitrarily large fixed girth. We prove that Matching Cut and Disconnected Perfect Matching are also -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 $$d\ge 1$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>d</mml:mi> <mml:mo>≥</mml:mo> <mml:mn>1</mml:mn> </mml:mrow> </mml:math> , is -complete for bipartite graphs of arbitrarily large fixed girth and bounded maximum degree. Furthermore, we show that Matching Cut , Perfect Matching Cut and Disconnected Perfect Matching are -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 with each other, and with a known and full classification of the Maximum Matching Cut problem, which is to determine a largest matching cut of a graph G . Finally, by combining existing results, we obtain a complete complexity classification of Perfect Matching Cut for $$\mathcal{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> -subgraph-free graphs where $$\mathcal{H}$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mi>H</mml:mi> </mml:math> is any finite set of graphs.