The cluster deletion problem for cographs

We prove new structural properties of cographs which characterize how a largest clique interacts with the rest of the graph. These results imply a remarkably simple polynomial time algorithm for Cluster Deletion on cographs. In contrast, we observe that Cluster Deletion remains NP-hard on a hereditary graph class which is slightly larger than cographs.