On stable cutsets in line graphs

DOI10.1016/S0304-3975(03)00048-3zbMath1022.68102MaRDI QIDQ1400002

Van Bang Le, Bert Randerath

Publication date: 30 July 2003

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

zbMATH Keywords

stable setsline graphscutsetsdecomposable graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items

Algorithms Solving the Matching Cut Problem ⋮ Finding matching cuts in \(H\)-free graphs ⋮ Maximum number of colors: C-coloring and related problems ⋮ Matching cut: kernelization, single-exponential time FPT, and exact exponential algorithms ⋮ Algorithms solving the matching cut problem ⋮ Improper C-colorings of graphs ⋮ Unnamed Item ⋮ 3-consecutive edge coloring of a graph ⋮ On stable cutsets in claw-free graphs and planar graphs ⋮ A complexity dichotomy for matching cut in (bipartite) graphs of fixed diameter ⋮ Matching cutsets in graphs of diameter 2 ⋮ Satisfactory graph partition, variants, and generalizations ⋮ Finding cuts of bounded degree: complexity, FPT and exact algorithms, and kernelization ⋮ Matching cut in graphs with large minimum degree ⋮ Covering graphs with convex sets and partitioning graphs into convex sets ⋮ The complexity of the matching-cut problem for planar graphs and other graph classes ⋮ Extremal graphs having no matching cuts ⋮ On the complexity of matching cut for graphs of bounded radius and \(H\)-free graphs ⋮ A note on matching-cut in \(P_t\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Decomposition by clique separators
• An algorithm for finding clique cut-sets
• Coloring graphs with stable cutsets
• Stable set bonding in perfect graphs and parity 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
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Matching cutsets in graphs