Characterizations for co-graphs defined by restricted NLC-width or clique-width operations

摘要

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)-free. Since (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)-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 P4, 2K2, and co-2P3.