The complexity of the perfect matching-cut problem

DOI10.1002/JGT.23167MaRDI QIDQ6667583zbMATH OpenFDO

Authors Valentin Bouquet, Christophe Picouleau

Publication date 20 January 2025

Published in Journal of Graph Theory (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial 4.0 International

zbMATH Keywords

matchingtreewidthNP-completeperfect matchingplanar graphpolynomialclaw-freeedge-cut

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• The perfect matching cut problem revisited
• The complexity of the matching-cut problem for planar graphs and other graph classes (extended abstract)
• The complexity of the matching-cut problem for planar graphs and other graph classes
• On the complexity of matching cut in graphs of fixed diameter
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter

Cites work

• scientific article; zbMATH DE number 1202982 (Why is no real title available?)
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Disconnected 2-factors in planar cubic bridgeless graphs
• Dominating cliques in \(P_ 5\)-free graphs
• Extremal graphs having no matching cuts
• Finding matching cuts in \(H\)-free graphs
• Graph structure and monadic second-order logic. A language-theoretic approach
• Graph theory
• Graphs with 1-Factors
• Matching cutsets in graphs
• On stable cutsets in line graphs
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• The perfect matching cut problem revisited

Cited in

(3)

• The perfect matching cut problem revisited
• Perfectly matched sets in graphs: parameterized and exact computation
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs

This page was built for publication: The complexity of the perfect matching-cut problem

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