Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4651492 | Discrete Mathematics | 2006 | 7 Pages |
In this paper we characterize subclasses of co-graphs defined by restricted NLC-width operations and subclasses of co-graphs defined by restricted clique-width operations.We show that a graph has NLCT-width 1 if and only if it is (C4,P4)(C4,P4)-free. Since (C4,P4)(C4,P4)-free graphs are exactly trivially perfect graphs, the set of graphs of NLCT-width 1 is equal to the set of trivially perfect graphs, and a recursive definition for trivially perfect graphs follows. Further we show that a graph has linear NLC-width 1 if and only if is (C4,P4,2K2)(C4,P4,2K2)-free. This implies that the set of graphs of linear NLC-width 1 is equal to the set of threshold graphs.We also give forbidden induced subgraph characterizations for co-graphs defined by restricted clique-width operations using P4P4, 2K22K2, and co-2P32P3.