On the stability number of AH‐free graphs
Alain Hertz, D. de Werra · Journal of Graph Theory · 1993
Abstract We describe a new class of graphs for which the stability number can be obtained in polynomial time. The algorithm is based on an iterative procedure that, at each step, builds from a graph G a new graph Gl that has fewer nodes and has the property that α(Gl) = α(G) − 1. This new class of graphs is different from the known classes for which the stability number can be computed in polynomial time. © 1993 John Wiley & Sons, Inc.