AbstractWe 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 graphGa new graphGlthat 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,