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

DOI10.1016/J.TCS.2022.09.014MaRDI QIDQ2087455zbMATH OpenOpenAlexFDO

Authors Felicia Lucke, Daniël Paulusma, Bernard Ries

Publication date 21 October 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

complexity dichotomyradius\(H\)-freematching cut

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On the complexity of matching cut in graphs of fixed diameter
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• A note on matching-cut in \(P_t\)-free graphs
• The complexity of the perfect matching-cut problem
• Algorithms solving the matching cut problem

Cites work

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

Cited in

(6)

• Finding matching cuts in \(H\)-free graphs
• Cutting Barnette graphs perfectly is hard
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• On The Complexity of Matching Cut for Graphs of Bounded Radius and $H$-Free Graphs
• Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
• A note on matching-cut in \(P_t\)-free graphs

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

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