Partitioning cographs into cliques and stable sets

We consider the problem of partitioning the node set of a graph into p cliques and k stable sets, namely the (p,k)-coloring problem. Results have been obtained for general graphs [Feder et al., SIAM J. Discrete Math. 16 (3) (2003) 449-478], chordal graphs [Hell et al., Discrete Appl. Math. 141 (2004) 185-194] and cacti for the case where k=p in [Ekim and de Werra, On split-coloring problems, submitted for publication] where some upper and lower bounds on the optimal value minimizing k are also presented. We focus on cographs and devise some efficient algorithms for solving (p,k)-coloring problems and cocoloring problems in O(n2+nm) time and O(n3/2) time, respectively. We also give an algorithm for finding the maximum induced (p,k)-colorable subgraph. In addition to this, we present characterizations of (2,1)- and (2,2)-colorable cographs by forbidden configurations.