Stability number of bull- and chair-free graphs
From MaRDI portal
Publication:1208469
DOI10.1016/0166-218X(93)90032-JzbMath0773.05070OpenAlexW2044614108MaRDI QIDQ1208469
Caterina De Simone, Antonio Sassano
Publication date: 16 May 1993
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(93)90032-j
Extremal problems in graph theory (05C35) Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (25)
On the vertex packing problem ⋮ Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs ⋮ FORK-DECOMPOSITION OF DIRECT PRODUCT OF GRAPHS ⋮ Polynomially solvable cases for the maximum stable set problem ⋮ Claw-free graphs---a survey ⋮ On the use of Boolean methods for the computation of the stability number ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Chair-free Berge graphs are perfect ⋮ From matchings to independent sets ⋮ Stability number of bull- and chair-free graphs revisited ⋮ An augmenting graph approach to the stable set problem in \(P_{5}\)-free graphs ⋮ Struction revisited ⋮ Stable sets in two subclasses of banner-free graphs ⋮ Stability preserving transformations of graphs ⋮ Maximum weight independent sets in odd-hole-free graphs without dart or without bull ⋮ A polynomial algorithm to find an independent set of maximum weight in a fork-free graph ⋮ Augmenting graphs for independent sets ⋮ Augmenting chains in graphs without a skew star. ⋮ Polynomial algorithm for finding the largest independent sets in graphs without forks ⋮ The complexity of dissociation set problems in graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes ⋮ Stability in \(P_5\)- and banner-free graphs ⋮ Stable sets in certain \(P_6\)-free graphs ⋮ On the stable set problem in special \(P_{5}\)-free graphs ⋮ The maximum clique problem
Cites Work
- The struction of a graph: Application to CN-free graphs
- Quelques utilisations de la STRUCTION. (Some applications of STRUCTION)
- Matching theory
- Bull-free Berge graphs are perfect
- On maximal independent sets of vertices in claw-free graphs
- Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
- On the vertex packing problem
- A polynomial algorithm for maximum weighted vertex packings on graphs without long odd cycles
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: Stability number of bull- and chair-free graphs
