On variations of P4-sparse graphs

✍ Scribed by Andreas Brandstädt; Raffaele Mosca

• Book ID: 104294157
• Publisher: Elsevier Science
• Year: 2003
• Tongue: English
• Weight: 206 KB
• Volume: 129
• Category: Article
• ISSN: 0166-218X
• DOI: 10.1016/s0166-218x(03)00180-x

✦ Synopsis

Ho ang deÿned the P4-sparse graphs as the graphs where every set of ÿve 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 classiÿcation with respect to clique-width of all superclasses of P4-sparse graphs deÿned 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 deÿned 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.