Stability number of bull- and chair-free graphs (Q1208469)

The authors regard finite, undirected, loopless, and connected graphs. A stable set in a graph is set of vertices, no two of which are adjacent. The size of the largest stable set of \(G\) is called the stability number. A bull is a graph with vertices \(a,b,c,d,e\) and edges \(ab,ac,bc,ad,be\); and a chair is a graph with vertices \(a,b,c,d,e\) and edges \(ab,bc,cd,be\). The problem of finding a stable set of maximum size in a graph is NP-hard. The authors define a class of graphs which is closed under taking induced subgraphs and contains imperfect graphs and graphs with induced claws. For these graphs the authors describe a polynomial time algorithm to find the stability number. This algorithm is a iterative procedure which, at each step, builds from a graph \(G\) a new graph \(G'\) which has fewer vertices and has the property that the stability number of \(G'\) is equal to stability number of \(G\) minus 1.