Forbidden graphs for tree-depth

For every k≥0k≥0, we define GkGk as the class of graphs with tree-depth at most kk, i.e. the class containing every graph GG admitting a valid colouring ρ:V(G)→{1,…,k}ρ:V(G)→{1,…,k} such that every (x,y)(x,y)-path between two vertices where ρ(x)=ρ(y)ρ(x)=ρ(y) contains a vertex zz where ρ(z)>ρ(x)ρ(z)>ρ(x). In this paper, we study the set of graphs not belonging in GkGk that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of GkGk). We determine these sets for k≤3k≤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 GkGk and we prove that there are exactly 1222k−1−k(1+22k−1−k). Finally, we prove that each obstruction of GkGk has at most 22k−122k−1 vertices.