On the use of Boolean methods for the computation of the stability number (Q1363750)

The author provides a polynomial time algorithm for the determination of the stability number of a graph which contains neither an induced chordless cycle with four vertices nor its complement. The algorithm is based on the transformation of a graph \(G= (V,E)\) with the above property into a graph \(G'= (V',E')\) with \(|V'|=|V |-1\) and the same stability number. This transformation has been obtained by using pseudo-Boolean techniques. Some applications are given.