Subgraph isomorphism on graph classes that exclude a substructure We study Subgraph Isomorphism on graph classes defined by a fixed forbidden graph. Although there are several ways for forbidding a graph, we observe that it is reasonable to focus on the minor relation since other wellknown relations lead to either trivial or equivalent problems. When the forbidden minor is connected, we present a near dichotomy of the complexity of Subgraph Isomorphism with respect to the forbidden minor, where the only unsettled case is the path of five vertices. We then also consider the general case of possibly disconnected forbidden minors. We show in particular that: the problem is fixedparameter tractable parameterized by the size of the forbidden minor H when H is a linear forest such that at most one component has four vertices and all other components have three or less vertices; and it is NPcomplete if H contains four or more components with at least five vertices each. As a byproduct, we show that Subgraph Isomorphism is fixedparameter tractable parameterized by vertex integrity. Using similar techniques, we also observe that Subgraph Isomorphism is fixedparameter tractable parameterized by neighborhood diversity.

Partitioning Cographs into Two Forests and One Independent Set We consider a variation of arboricity, where a graph is partitioned into p forests and q independent sets. These problems are NPcomplete in general, but polynomialtime solvable in the class of cographs; in fact, for each p and q there are only finitely many minimal nonpartitionable cographs. In previous investigations it was revealed that when (p0) or (p1), these minimal nonpartitionable cographs can be uniformly described as one family of obstructions valid for all values of q. We investigate the next case, when (p2); we provide the complete family of minimal obstructions for (p2, q1), and find that they include more than just the natural extensions of the previously described obstructions for (p2, q0). Thus a uniform description for all q seems unlikely already in the case (p2).