Obstructions for Tree-depth

For every k⩾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 class obs(Gk) of minor-minimal elements not belonging in Gk for every k⩾0. We give a precise characterization of Gk,k⩽3 and prove a structural lemma for creating graphs G∈obs(Gk), k>0. As a consequence, we obtain a precise characterization of all acyclic graphs in obs(Gk) and we prove that they are exactly .