On the stability number of claw-free P-5-free and more general graphs

In this note we show that the stability number of a (4-pan, chair, K-1,K-4, P-5)-free graph which has no simplicial vertex is bounded by 3. This genera lizes the case of (claw, P-5)-free graphs and leads to a very simple polyno mial-time algorithm for determining the stability number of (claw, Ps)-free graphs and, more generally, of (4-pan,chair, K-1,K-4, P-5)-free graphs. (C ) 1999 Elsevier Science B.V. All rights reserved.