Abstrakt
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 rho : V(G) -> {1, ... , k} such that every (x, y)-path between two vertices where rho(x) = rho(y) contains a vertex z where rho(z) > rho(x). In this paper, we study the set of graphs not belonging in G(k) that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of G(k)).
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 G(k) and we prove that there are exactly 1/2 2(2k-1-k)(1+2(2k-1-k)).
Finally, we prove that each obstruction of G(k) has at most 2(2k-1) vertices.