On the structure and stability number Of P5- and co-chair-free graphs

We give a O(nm) time algorithm for the maximum weight stable set (MWS) problem on P-5- and co-chair-free graphs without recognizing whether the (arbitrary) input graph is P-5- and co-chair-free. This algorithm is based on the fact that prime P-5- and co-chair-free graphs containing 2K(2) are matched co-bipartite graphs and thus have very simple structure, and for 2K(2)-free graphs, there is a polynomial time algorithm for the MWS problem due to a result of Farber saying that 2K(2)-free graphs contain at most O(n(2)) maximal stable sets. A similar argument can be used for (P-5,co-P)-free graphs; their prime graphs are 2K(2)-free. Moreover, we give a complete classification Of (P5,co-chair,H)-free graphs with respect to their clique width when H is a one-vertex P-4 extension; this extends the characterization Of (P-5,(P) over bar (5),co-chair)-free graphs called semi-P-4-sparse by Fouquet and Giakoumakis. For H being a house, P, bull or gem, the class of (P-5,co-chair,H)-free graphs has bounded clique width and very simple structure whereas for the other four cases, namely H being a co-gem, chair, co-P or C-5, the class has unbounded clique width due to a result of Makowsky and Rotics. Bounded clique width implies linear time algorithms for all algorithmic problems expressible in LinEMSOL a variant of Monadic Second Order Logic including the MWS Problem. (C) 2003 Elsevier B.V. All rights reserved.