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.

Given nonnegative integers, s and k, an (s, k)-polar partition of a graph G is a partition (A, B) of VG such that G[A] and ̅G[B] are complete multipartite graphs with at most s and k parts, respectively. If s or k is replaced by ∞, it means that there is no restriction on the number of parts of G[A] or ̅G[B], respectively. A split graph is a graph admitting a (1, 1)-polar partition. A graph is said to be unipolar or monopolar if its vertex set admits an (∞, ∞)-polar partition (A, B) such that A is a clique or an independent set, respectively. Naturally, most problems related to polar partitions are trivial on split graphs, even when some of them are very hard in general. In this work, we present some results related to polar partitions on two graph classes generalizing split graphs. Our main results include efficient algorithms to decide whether a graph on these classes admits such partitions, as well as upper bounds for the order of minimal (s, k)-polar obstructions on such graph families for any s and k (even if s or k is ∞).

A (2, 1)-colouring of a graph is a partition of its vertex set into two independent sets and a clique (any of which may be empty). We present forbidden induced subgraph characterizations for some hereditary graph classes obtained from (2, 1)-colouring by adding restrictions between its parts (e.g., there are no edges between the clique and one of the independent sets). The obtained characterizations yield certifying algorithms to recognize these graph classes, which run in time O(|V| + |E|). All the algorithms presented are straightforward to implement using basic data structures.