The complexity of the matching-cut problem for planar graphs and other graph classes

DOI10.1002/jgt.20390zbMath1179.05104OpenAlexW2738197751MaRDI QIDQ3652545

Paul Bonsma

Publication date: 18 December 2009

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

Full work available at URL: https://research.utwente.nl/en/publications/the-complexity-of-the-matchingcut-problem-for-planar-graphs-and-other-graph-classes(653f313a-e872-4ba4-8abb-3eb9f82f8fbb).html

zbMATH Keywords

computational complexityplanar graphedge cutmatching-cutdecomposable graph recognition problem

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (23)

Vertex partitioning problems on graphs with bounded tree width ⋮ Algorithms Solving the Matching Cut Problem ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Parameterized complexity of perfectly matched sets ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Maximum number of colors: C-coloring and related problems ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ Algorithms solving the matching cut problem ⋮ Improper C-colorings of graphs ⋮ \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs ⋮ Unnamed Item ⋮ Perfectly matched sets in graphs: parameterized and exact computation ⋮ A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter ⋮ Combinatorial optimization with interaction costs: complexity and solvable cases ⋮ Good edge-labelling of graphs ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ The perfect matching cut problem revisited ⋮ The perfect matching cut problem revisited ⋮ Matching cut in graphs with large minimum degree ⋮ Extremal graphs having no matching cuts ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs ⋮ A note on matching-cut in \(P_t\)-free graphs ⋮ An FPT algorithm for matching cut and d-cut

Cites Work

• Unnamed Item
• Some simplified NP-complete graph problems
• On stable cutsets in line graphs
• On stable cutsets in graphs
• Forbidden subgraph decomposition
• Linear time solvable optimization problems on graphs of bounded clique-width
• Approximating clique-width and branch-width
• Recognizing decomposable graphs
• Easy problems for tree-decomposable graphs
• Networks immune to isolated line failures
• Matching cutsets in graphs
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: The complexity of the matching-cut problem for planar graphs and other graph classes