A note on \(\alpha\)-redundant vertices in graphs

DOI10.1016/S0166-218X(00)00239-0zbMath0968.05058MaRDI QIDQ5929313

Andreas Brandstädt, Vadim V. Lozin

Publication date: 3 September 2001

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

zbMATH Keywords

graphindependence numberredundant vertexstability number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (23)

Solving Problems on Graphs of High Rank-Width ⋮ On independent vertex sets in subclasses of apple-free graphs ⋮ The maximum independent set problem in subclasses of \(S_{i, j, k}\)-free graphs ⋮ Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ On easy and hard hereditary classes of graphs with respect to the independent set problem ⋮ On the structure and stability number of \(P_{5}\)- and co-chair-free graphs ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ Solving problems on graphs of high rank-width ⋮ Stability preserving transformations of graphs ⋮ Stabex method for extension of \(\alpha\)-polynomial hereditary classes. ⋮ Stable sets of maximum weight in (\(P_{7}\), banner)-free graphs ⋮ On clique separators, nearly chordal graphs, and the Maximum Weight Stable Set Problem ⋮ On sequential heuristic methods for the maximum independent set problem ⋮ Stability number in subclasses of \(P_5\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Maximum independent sets in subclasses of \(P_{5}\)-free graphs ⋮ On the maximum independent set problem in graphs of bounded maximum degree ⋮ Extending the MAX algorithm for maximum independent set ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ On the stable set problem in special \(P_{5}\)-free graphs ⋮ On \(\alpha\)-redundant vertices in \(P_{5}\)-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
• On the stability number of claw-free \(P_5\)-free and more general graphs
• Stability in \(P_5\)- and banner-free graphs
• Polynomially solvable cases for the maximum stable set problem
• A Linear Recognition Algorithm for Cographs
• Stability in circular arc graphs
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph

This page was built for publication: A note on \(\alpha\)-redundant vertices in graphs