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 Sbihi's theorem on the stability number problem in claw-free graphs. Also, a recent result of Lozin on stability in (P5,P)-free graphs is a corollary of our result.