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.

The dichromatic number of a digraph D is the minimum number of colors of a vertex coloring of D such that D has no monochromatic cycles, the dichromatic number is an extension of the chromatic number to the class of digraphs. The Hajós join is a tool to obtain r-chromatic graphs, using the dichromatic number, J. Bang-Jensen et. al. extended the Hajós join to digraphs, and thus obtained a tool to obtain r-dichromatic digraphs. J. Bang-Jensen et. al. posed in 2020 the problem of how to obtain the symmetric cycle of length 5 from symmetric cycles of length 3. We recently solved this problem by applying a genetic algorithm. In this article, we generalize the construction of the symmetric cycle of length 5 and determine the computational complexity as Θ(n ln(n)).