On variations of P4-sparse graphs
Hong defined the P4-sparse graphs as the graphs where every set of five vertices induces at most one P4. These graphs attracted considerable attention in connection with the P4-structure of graphs and the fact that P4-sparse graphs have bounded clique-width. Fouquet and Giakoumakis generalized this class to the nicely structured semi-P4-sparse graphs being the (P5, co-P5, co-chair)-free graphs. We give a complete classification with respect to clique-width of all superclasses of P4-sparse graphs defined by forbidden P4 extensions by one vertex which are not P4-sparse, i.e. the P5, chair, P, C5 as well as their complements. It turns out that there are exactly two other inclusion-maximal classes defined by three or four forbidden P4 extensions namely the (P5, P, co-chair)-free graphs and the (P, co-P, chair, co-chair)-free graphs which also deserve the name semi-P4-sparse.
p4-sparse graphs clique-width prime graphs linear time algorithms monadic second-order logic