<oai_dc:dc xmlns:dc="http://purl.org/dc/elements/1.1/" xmlns:oai_dc="http://www.openarchives.org/OAI/2.0/oai_dc/" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:schemaLocation="http://www.openarchives.org/OAI/2.0/oai_dc/ http://www.openarchives.org/OAI/2.0/oai_dc.xsd">
  <dc:creator>Feghali, Carl</dc:creator>
  <dc:creator>Lucke, Felicia</dc:creator>
  <dc:creator>Paulusma, Daniël</dc:creator>
  <dc:creator>Ries, Bernard</dc:creator>
  <dc:date>2023</dc:date>
  <dc:description xmlns:ns0="xml" ns0:lang="en">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 d ≥ 1, is NP-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 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 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 H-subgraph-free graphs where H is any finite set of graphs.</dc:description>
  <dc:format>application/pdf</dc:format>
  <dc:identifier>https://folia.unifr.ch/global/documents/329096</dc:identifier>
  <dc:identifier>https://folia.unifr.ch/documents/329096/files/lipics.isaac.2023.31.pdf</dc:identifier>
  <dc:language>eng</dc:language>
  <dc:publisher>Schloss Dagstuhl – Leibniz-Zentrum für Informatik</dc:publisher>
  <dc:relation>info:eu-repo/semantics/altIdentifier/doi/10.4230/LIPIcs.ISAAC.2023.31</dc:relation>
  <dc:relation>info:eu-repo/semantics/altIdentifier/issn/1868-8969</dc:relation>
  <dc:rights>info:eu-repo/semantics/openAccess</dc:rights>
  <dc:rights>License undefined</dc:rights>
  <dc:source>34th International Symposium on Algorithms and Computation (ISAAC 2023). - Leibniz International Proceedings in Informatics (LIPIcs). - 2023, vol. 283, no. 31, p. 31:1–31:16</dc:source>
  <dc:subject xmlns:ns1="xml" ns1:lang="en">matching cut</dc:subject>
  <dc:subject xmlns:ns2="xml" ns2:lang="en">perfect matching</dc:subject>
  <dc:subject xmlns:ns3="xml" ns3:lang="en">girth</dc:subject>
  <dc:subject xmlns:ns4="xml" ns4:lang="en">H-free graph</dc:subject>
  <dc:subject>info:eu-repo/classification/udc/004</dc:subject>
  <dc:title xmlns:ns5="xml" ns5:lang="en">Matching Cuts in Graphs of High Girth and H-Free Graphs</dc:title>
  <dc:type>http://purl.org/coar/resource_type/c_6501</dc:type>
</oai_dc:dc>