
Abstract 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 Brandstadt in [A. Bransdstadt, 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. Brandstadt 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.
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 9 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
