On stable cutsets in graphs

DOI10.1016/S0166-218X(00)00197-9zbMath0962.68138OpenAlexW1967755743MaRDI QIDQ1582067

Thomas Szymczak, Van Bang Le, Feodor F. Dragan, Andreas Brandstädt

Publication date: 13 June 2001

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(00)00197-9

zbMATH Keywords

efficient algorithmshole-free graphsbrittle graphsstable cutset

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (22)

Stable skew partition problem ⋮ On equistable, split, CIS, and related classes of graphs ⋮ Vertex partitioning problems on graphs with bounded tree width ⋮ Algorithms Solving the Matching Cut Problem ⋮ Minimal Disconnected Cuts in Planar Graphs ⋮ A new characterization of unichord-free graphs ⋮ 3-colouring AT-free graphs in polynomial time ⋮ On stable cutsets in line graphs ⋮ Algorithms solving the matching cut problem ⋮ Parameterizing cut sets in a graph by the number of their components ⋮ 3-consecutive edge coloring of a graph ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ Matching cutsets in graphs of diameter 2 ⋮ The polynomial dichotomy for three nonempty part sandwich problems ⋮ The P versus NP-complete dichotomy of some challenging problems in graph theory ⋮ The computational complexity of disconnected cut and \(2 K_2\)-partition ⋮ The sandwich problem for cutsets: clique cutset, \(k\)-star cutset ⋮ The complexity of list edge-partitions for simple graphs ⋮ The sandwich problem for decompositions and almost monotone properties ⋮ Unnamed Item ⋮ The complexity of the matching-cut problem for planar graphs and other graph classes ⋮ Bisplit graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chordality properties on graphs and minimal conceptual connections in semantic data models
• On rigid circuit graphs
• An algorithm for finding clique cut-sets
• Coloring graphs with stable cutsets
• Finding large holes
• Stable set bonding in perfect graphs and parity graphs
• Complexity of graph partition problems
• Representation of a finite graph by a set of intervals on the real line
• Recognizing decomposable graphs
• On brittle graphs
• Graph Classes: A Survey
• Asteroidal Triple-Free Graphs
• Matching cutsets in graphs
• The complexity of satisfiability problems

This page was built for publication: On stable cutsets in graphs