On stable cutsets in claw-free graphs and planar graphs

DOI10.1016/j.jda.2007.04.001zbMath1154.05317OpenAlexW1970916146MaRDI QIDQ935842

Haiko Müller, Van Bang Le, Raffaele Mosca

Publication date: 8 August 2008

Published in: Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jda.2007.04.001

zbMATH Keywords

claw-free graphplanar graphmatching-cutstable cutset

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Vertex partitioning problems on graphs with bounded tree width ⋮ On polynomial kernelization of \(\mathcal H\)-\textsc{free edge deletion} ⋮ Algorithms Solving the Matching Cut Problem ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ Algorithms solving the matching cut problem ⋮ Dominating induced matchings in graphs without a skew star ⋮ 3-consecutive edge coloring of a graph ⋮ Satisfactory graph partition, variants, and generalizations

Cites Work

• New applications of clique separator decomposition for the maximum weight stable set problem
• Decomposition by clique separators
• Rectilinear planar layouts and bipolar orientations of planar graphs
• An algorithm for finding clique cut-sets
• Coloring graphs with stable cutsets
• Algorithms on clique separable graphs
• Stable set bonding in perfect graphs and parity graphs
• A special planar satisfiability problem and a consequence of its NP- completeness
• On stable cutsets in line graphs
• On stable cutsets in graphs
• A note on fragile graphs
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Recognizing decomposable graphs
• Networks immune to isolated line failures
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• List Partitions
• A Split&Push Approach to 3D Orthogonal Drawing
• Fragile graphs with small independent cuts
• Matching cutsets in graphs
• ON PRIMITIVE GRAPHS AND OPTIMAL VERTEX ASSIGNMENTS
• Graph-Theoretic Concepts in Computer Science
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item