Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
10328489 | Discrete Applied Mathematics | 2005 | 12 Pages |
Abstract
We give a complete structure description of (P5,gem)-free graphs. By the results of a related paper, this implies bounded clique width for this graph class. Hereby, as usual, the P5 is the induced path with five vertices a,b,c,d,e and four edges ab,bc,cd,de, and the gem consists of a P4a,b,c,d with edges ab,bc,cd plus a universal vertex e adjacent to a,b,c,d.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Andreas Brandstädt, Dieter Kratsch,