Stability number of bull- and chair-free graphs revisited

DOI10.1016/S0166-218X(02)00415-8zbMath1029.05077OpenAlexW2067731498MaRDI QIDQ1408811

Chính T. Hoàng, Andreas Brandstädt, Van Bang Le

Publication date: 25 September 2003

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

Full work available at URL: https://doi.org/10.1016/s0166-218x(02)00415-8

zbMATH Keywords

independence numberstability numberprime graphclique widthbull graphchair graph

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (11)

Unnamed Item ⋮ Maximum weight independent sets in classes related to claw-free graphs ⋮ New applications of clique separator decomposition for the maximum weight stable set problem ⋮ Hereditary Efficiently Dominatable Graphs ⋮ On variations of \(P_{4}\)-sparse 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 ⋮ Bounding \(\chi \) in terms of \(\omega \) and \(\varDelta \) for some classes of graphs ⋮ On minimal prime extensions of a four-vertex graph in a prime graph ⋮ The stable set polytope for some extensions of \(P_4\)-free graphs ⋮ Efficient robust algorithms for the maximum weight stable set problem in chair-free graph classes

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On maximal independent sets of vertices in claw-free graphs
• Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
• Complement reducible graphs
• A tree representation for \(P_ 4\)-sparse graphs
• Stability number of bull- and chair-free graphs
• On the \(p\)-connectedness of graphs---a survey
• A decomposition for a class of \((P_ 5,\overline{P}_ 5)\)-free graphs
• Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
• On graphs without \(P_ 5\) and \(\overline {P}_ 5\)
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• On the vertex packing problem
• Handle-rewriting hypergraph grammars
• A Linear Recognition Algorithm for Cographs
• Graph Classes: A Survey
• Polynomial algorithm for finding the largest independent sets in graphs without forks
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES

This page was built for publication: Stability number of bull- and chair-free graphs revisited