Publication
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 \cite{hellcomp}, chordal graphs \cite{hellchordal} and cacti for the case where k=p in \cite{tidosplit} 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(n^2+nm) time and O(n^{3/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.