Characterizing (k,l)-partitionable Cographs

We consider the problem of partitioning a graph into k independent sets and l cliques, known as the (k,l)-partition problem, which was introduced by Brandstädt in [A. Bransdstädt, Partitions of graphs into one or two independent sets and cliques, Discrete Mathematics 152 (1996) 47-54], and generalized by Feder et al. in [T. Feder, P. Hell, S. Klein, and R. Motwani, Complexity of graph partition problems, in: Thirty First Annual ACM Symposium on Theory of Computing (1999), Plenum Press, New York, 1999, 464-472] as the M-partition problem. Brandstädt proved that given a graph G, it is NP-complete to decide if G is a (k,l)-graph for k≥3 or l≥3. Since then, a lot of work have been done in order to solve the (k,l)-partition problem for many subclasses of perfect graphs. In this work, we consider a subclass of perfect graphs: the cographs, which correspond to graphs without paths with size 4. More precisely, we provide a characterization of cographs that are (k,l)-graphs by forbidden configurations, that is, a cograph G is a (k,l)-graph if and only if it does not contain any of the forbbiden configurations.