Stability number in subclasses of \(P_5\)-free graphs
type: Item
instance of: scholarly article
title: Stability number in subclasses of \(P_5\)-free graphs
zbMATH Open document ID: 1057.05063
published in: Applied Mathematics. Series B (English Edition)
publication date: 2005-02-24T00:00:00Z
review text: The stability number or independence number of a graph \(G\) is the maximum cardinality among the independent sets of vertices of \(G\). The authors present two new hereditary classes of \(P_5\)-free graphs where the stability number can be found in polynomial time. These results generalize several known ones.
reviewed by: Lutz Volkmann
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 2138461
zbMATH Keywords: stability number
zbMATH Keywords: \(P_5\)-free graphs
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: hereditary classes
author: I.È. Zverovich
author: Olga I. Zverovich
MaRDI profile type: Publication
full work available at URL: s11766-004-0045-6
OpenAlex ID: W2039180066
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: On the stability number of claw-free \(P_5\)-free and more general graphs
cites work: A note on \(\alpha\)-redundant vertices in graphs
cites work: On semi-\(P_ 4\)-sparse graphs
cites work: Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
cites work: Weighted parameters in \((P_5,\overline {P_5})\)-free graphs
cites work: Construction of a Maximum Stable Set with $k$-Extensions
cites work: Q4505839
cites work: On the use of Boolean methods for the computation of the stability number
cites work: Stability in \(P_5\)- and banner-free graphs
cites work: Polynomial algorithms for the maximum stable set problem on particular classes of \(P_{5}\)-free graphs
cites work: Q4871056
cites work: Q4780523
cites work: Extension of hereditary classes with substitutions
cites work: Minimum degree algorithms for stability number
cites work: Stabex method for extension of \(\alpha\)-polynomial hereditary classes.
cites work: Penta-extensions of hereditary classes of graphs
DOI: 10.1007/S11766-004-0045-6
description: scientific article; zbMATH DE number 2138461