Matching cutsets in graphs of diameter 2

DOI10.1016/J.TCS.2008.07.002MaRDI QIDQ955037zbMATH OpenOpenAlexFDO

Authors Mieczysław Borowiecki, Katarzyna Jesse-Józefczyk

Publication date 18 November 2008

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

Full work available at URL https://doi.org/10.1016/j.tcs.2008.07.002

zbMATH Keywords

graph algorithmsstable cutsetmatching cutset

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Matching cutsets in graphs
• On the complexity of matching cut in graphs of fixed diameter
• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• Matchings in graphs with a given number of cuts
• Matching cut in graphs with large minimum degree
• Matching cut in graphs with large minimum degree
• On tight cuts in matching covered graphs
• On cuts and matchings in planar graphs
• A note on tight cuts in matching-covered graphs
• Finding matching cuts in \(H\)-free graphs

Cites work

• scientific article; zbMATH DE number 1003286 (Why is no real title available?)
• scientific article; zbMATH DE number 1456953 (Why is no real title available?)
• Coloring graphs with stable cutsets
• Efficient and practical algorithms for sequential modular decomposition
• Graphs of diameter two with no 4-circuits
• Matching cutsets in graphs
• Maximal and minimal vertex-critical graphs of diameter two
• Modular decomposition and transitive orientation
• On stable cutsets in graphs
• On stable cutsets in line graphs
• Recognizing decomposable graphs
• Size in maximal triangle-free graphs and minimal graphs of diameter 2
• Stable set bonding in perfect graphs and parity graphs
• Sufficient conditions for \(\lambda'\)-optimality in graphs of diameter 2

Cited in

(15)

• A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter
• On the complexity of matching cut in graphs of fixed diameter
• 3-consecutive edge coloring of a graph
• On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs
• Dichotomies for maximum matching cut: \(H\)-freeness, bounded diameter, bounded radius
• Finding matching cuts in \(H\)-free graphs
• Algorithms solving the matching cut problem
• Satisfactory graph partition, variants, and generalizations
• Vertex partitioning problems on graphs with bounded tree width
• Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms
• Matching cut in graphs with large minimum degree
• Algorithms Solving the Matching Cut Problem
• scientific article; zbMATH DE number 7378605 (Why is no real title available?)
• Improper C-colorings of graphs
• \(\boldsymbol{(\alpha, \beta )}\)-Modules in Graphs

This page was built for publication: Matching cutsets in graphs of diameter 2

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