On the stability number of claw-free P₅-free and more general graphs

DOI10.1016/S0166-218X(99)00072-4zbMATH Open1113.05308WikidataQ127955373 ScholiaQ127955373MaRDI QIDQ1302154FDOQ1302154

Authors 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

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

Recommendations

• Stability number in subclasses of \(P_5\)-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• scientific article; zbMATH DE number 1208717
• On the stable set problem in special \(P_{5}\)-free graphs
• Stable sets in \(k\)-colorable \(P_{5}\)-free graphs

Cited in

(18)

• New applications of clique separator decomposition for the maximum weight stable set problem
• A note on \(\alpha\)-redundant vertices in graphs
• \(P_{5}\)-free augmenting graphs and the maximum stable set problem
• An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs
• Stability in \(P_5\)- and banner-free graphs
• Some results on maximum stable sets in certain \(P_{5}\)-free graphs
• Some results on graphs without long induced paths
• On the stable set problem in special \(P_{5}\)-free graphs
• The struction of a graph: Application to CN-free graphs
• On the structure and stability number of \(P_{5}\)- and co-chair-free graphs
• Stable sets in two subclasses of banner-free graphs
• Some observations on maximum weight stable sets in certain \(P_{5}\)-free graphs
• On 3-stable number conditions in \(n\)-connected claw-free graphs
• Struction revisited
• Some new hereditary classes where graph coloring remains NP-hard
• Independent sets in extensions of 2\(K_{2}\)-free graphs
• Stability number in subclasses of \(P_5\)-free graphs
• New sufficient conditions for \(\alpha\)-redundant vertices

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1302154)