We define the family of Maya-Tupi graphs as those graphs that admit a partition ( A, B) of their vertex sets such that A induces a complete multipartite graph where each part has size at most two, and B induces a graph where every connected component is K 1 or K 2 . The family of Maya-Tupi graphs is self complementary, generalizes split graphs, falls into the sparse-dense partitioning schema and is characterized by finitely many forbidden induced subgraphs. Unfortunately, our computational experiments show that the number of minimal forbidden induced subgraphs to characterize Maya-Tupi graphs is greater than 2000. In this work, we study Maya-Tupi graphs when restricted to some well-known graph classes. We find characterizations in terms of minimal forbidden induced subgraphs for disconnected graphs, trees and cographs; our results imply linear time certifying recognition algorithms for Maya-Tupi graphs within these classes. We also show that Maya-Tupi graphs can be recognized in O( n 3 )-time in C 4 -free graphs and in graphs with bounded neighborhood diversity.

Let G = (V, E) be a graph and k a positive integer such that k ≤ | V | . The k -token graph of G is the graph F k (G) having the set of all k -sets of V as vertex set, and such that two k -sets of V , say A and B , are adjacent if and only if the symmetric difference of A and B is an edge of G. In this work we study the cop number of token graphs of graphs in some classic families, such as paths, stars, and subdivided stars. We obtain the exact cop number for k -token graphs of paths and stars. We also obtain the exact cop number for subdivided stars when the number of branches is large enough. Probably more interesting than the aforementioned results, we introduce a variant of the Cops and Robbers game where R controls a team of robbers and C controls some teams of cops. A game of Cops and Robbers with this new variant played on a graph G is equivalent to a classic game of Cops and Robbers played on F k (G). This turns out to be very useful, as F k (G) is usually very large and complex when compared to G .

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.

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.

We unify two popular graph classes, strongly chordal graphs and chordal bigraphs, by introducing an umbrella class that contains both classes and maintains their essential properties. This is done by allowing loops at vertices. Considering loops often has little impact on a class of graphs; it however makes a big difference in this case. We call the new class \itstrongly chordal graphs with possible loops. When all vertices have loops, we recover the usual strongly chordal graphs; when all vertices are loopless, we obtain the usual chordal bigraphs. Moreover, there is a surprizing wealth of graphs in the new class that have loops at some vertices and not at others. These graphs also admit the elegant algorithms previously only applied in the extreme two cases. Formulated in the language of adjacency matrices, we study the class of symmetric 0, 1 matrices that admit a simultaneous row and column permutation avoiding the $\Gamma$ matrix $[ \begin{smallmatrix} 1 \ 1 \\ 1 \ 0 \end{smallmatrix}]$. We give ordering characterizations, matrix characterizations, and forbidden subgraph characterizations of the new class, and illustrate its usefulness by solving the minimum domination problem in this general context. This implies solutions of both the minimum dominating set in strongly chordal graphs and the minimum total dominating set in chordal bigraphs.