Structural characterization and decomposition for cographs-(2, 1) and (1, 2): a natural generalization of threshold graphs

A cograph is a graph without induced paths of length 4. A graph G is (2, 1) if its vertex set can be partitioned into at most 2 independent sets and 1 clique. Cographs-(k,ℓ) have already a characterization by forbidden subgraphs, but no structural characterization is known, except for cographs-(1, 1), i.e threshold graphs. In this paper, we present a structural characterization and a decomposition theorem for cographs-(2, 1) and, consequently, for cographs-(1, 2), leading to linear time recognition algorithms for both classes.