On variations of P4-sparse graphs

Hoang defined the P-4-sparse graphs as the graphs where every set of five vertices induces at most one P-4. These graphs attracted considerable attention in connection with the P-4-structure of graphs and the fact that P-4-sparse graphs have bounded clique-width. Fouquet and Giakoumakis generalized this class to the nicely structured semi-P-4-sparse graphs being the (P-5, co-P-5, co-chair)-free graphs. We give a complete classification with respect to clique-width of all superclasses of P-4-sparse graphs defined by forbidden P-4 extensions by one vertex which are not P-4-sparse, i.e. the P-5, chair, P, C-5 as well as their complements. It turns out that there are exactly two other inclusion-maximal classes defined by three or four forbidden P-4 extensions namely the (P-5, P, co-chair)-free graphs and the (P, co-P, chair, co-chair)-free graphs which also deserve the name semi-P-4-sparse. (C) 2003 Elsevier B.V. All rights reserved.