On the stability number of claw-free \(P_5\)-free and more general graphs

DOI10.1016/S0166-218X(99)00072-4zbMath1113.05308WikidataQ127955373 ScholiaQ127955373MaRDI QIDQ1302154

Andreas Brandstädt, Peter L. Hammer

Publication date: 22 September 1999

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

zbMATH Keywords

Independence numberClaw-free graphsPolynomial-time algorithmSimplicial verticesStability number

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (14)

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 ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ Struction revisited ⋮ \(P_{5}\)-free augmenting graphs and the maximum stable set problem ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Some results on maximum stable sets in certain \(P_{5}\)-free graphs ⋮ A note on \(\alpha\)-redundant vertices in graphs ⋮ Stability number in subclasses of \(P_5\)-free graphs ⋮ Independent sets in extensions of 2\(K_{2}\)-free graphs ⋮ Some new hereditary classes where graph coloring remains NP-hard ⋮ Some results on graphs without long induced paths ⋮ New sufficient conditions for \(\alpha\)-redundant vertices ⋮ On the stable set problem in special \(P_{5}\)-free graphs

This page was built for publication: On the stability number of claw-free \(P_5\)-free and more general graphs