On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs

DOI10.1016/J.TCS.2022.09.014OpenAlexW4296666778MaRDI QIDQ2087455

Felicia Lucke, Daniël Paulusma, Bernard Ries

Publication date: 21 October 2022

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2204.07129

zbMATH Keywords

radiuscomplexity dichotomy\(H\)-freematching cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Related Items (2)

Finding matching cuts in \(H\)-free graphs ⋮ Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths

Cites Work

• Unnamed Item
• Algorithms and almost tight results for 3-colorability of small diameter graphs
• A new characterization of \(P_k\)-free graphs
• Computing vertex-surjective homomorphisms to partially reflexive trees
• Algorithms solving the matching cut problem
• Matching cutsets in graphs of diameter 2
• A new characterization of \(P_{6}\)-free graphs
• On stable cutsets in line graphs
• On structural parameterizations of the matching cut problem
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• A note on matching-cut in \(P_t\)-free graphs
• An FPT algorithm for matching cut and d-cut
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Recognizing decomposable graphs
• The complexity of the matching-cut problem for planar graphs and other graph classes
• Networks immune to isolated line failures
• Matching cutsets in graphs
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• Good edge-labelling of graphs
• Matching cut in graphs with large minimum degree

This page was built for publication: On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs