Obstructions for Tree-depth

For every k ≥ 0, we define G_k 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 (G_k) of minor-minimal elements not belonging in G_k for every k ≥ 0. We give a precise characterization of G_k, k ≤ 3 and prove a structural lemma for creating graphs G ∈ obs (G_k), k > 0. As a consequence, we obtain a precise characterization of all acyclic graphs in obs (G_k) and we prove that they are exactly frac(1, 2) 2^{2k - 1 - k} (1 + 2^{2k - 1 - k}).