Forbidden graphs for tree-depth

For every kge. 0, we define Gk as the class of graphs with tree-depth at most k, i.e. the class containing every graph G admitting a valid colouring ρ :. V(G)→ {. 1, . . . , k} such that every (x, y)-path between two vertices where ρ (x) = ρ (y) contains a vertex z where ρ (z) > ρ (x). In this paper, we study the set of graphs not belonging in Gk that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of Gk). We determine these sets for k≤ 3 for each relation and prove a structural lemma for creating obstructions from simpler ones. As a consequence, we obtain a precise characterization of all acyclic obstructions of Gk and we prove that there are exactly 1222k-1-k(1+22k-1-k). Finally, we prove that each obstruction of Gk has at most 22k-1 vertices.