Maximum Weight Stable Set on graphs without claw and co-claw (and similar graph classes) can be solved in linear time. (Q1853148)

Minty has shown that the Maximum Weight Stable Set (MWS) Problem can be solved in polynomial time when restricted to claw-free graphs. We show that the structure of graphs being both claw-free and co-claw-free is very simple which implies bounded clique width for this graph class. It is known that for graph classes of bounded clique width (assuming that \(k\)-expressions can be determined in linear time), there are linear time algorithms for all problems expressible in Monadic Second Order Logic with quantification only over vertex sets. The problems MWS, Maximum Clique, Domination and Steiner Tree, for example, are expressible in this way. Moreover, we describe the structure of prime graphs being both \(H\)- and \(\overline H\)-free for any four-vertex graph \(H\) and obtain bounded clique width for these graph classes except the \(2K_{2}\)- and \(C_{4}\)-free graphs.