Stabex method for extension of ?-polynomial hereditary classes ?
A class of graphs is called ?-polynomial if there exists a polynomial-time algorithm for finding the stability number ?(G) for all graphs G in the class. We define a set Stabex(F,v) associated with a graph F and a vertex v?V(F). Let F be a minimal forbidden induced subgraph for an ?-polynomial hereditary class . It is shown that if we change F with Stabex(F,v) in the list of forbidden induced subgraphs for , then we obtain an ?-polynomial extension of . We obtain a generalization of Sbihis theorem [Discrete Math. 28(3) (1980) 53] on the stability number problem in claw-free graphs. Also, a recent result of Lozin [Eur. J. Oper. Res. 125 (2000) 292] on stability in (P5,P)-free graphs is a corollary of our result.
hereditary class polynomial-time algorithm stability number