An M9-partition of a graph is a partition of its vertex set into an independent set and a set inducing a complete bipartite graph, i.e. an M 9 -partition is a 3-coloring ( I, J, K) with the additional restriction that each vertex in part J is adjacent to all vertices in part K. A counipolar partition of a graph is a partition of its vertex set into an independent set and a set inducing a complete multipartite graph. In this work, we present partial results on the structure of the families of P 5 -free graphs admitting either a counipolar or an M9 -partition. Specifically, we focus on forbidden induced subgraph characterizations and recognition algorithms for these graph classes.

A kernel in a digraph is an independent and absorbent subset of its vertex set. A digraph is critical kernel imperfect if it does not have a kernel, but every proper induced subdigraph does. In this article, we characterize asymmetrical 4-quasi-transitive and 4-transitive digraphs, as well as 2-anti-transitive, and asymmetrical 4-anti-transitive digraphs with bounded diameter, which are critical kernel imperfect.