Forbidden graphs for tree-depth

Abstract: For every , we define as the class of graphs with tree-depth at most , i.e. the class containing every graph admitting a valid colouring such that every -path between two vertices where contains a vertex where . In this paper, we study the set of graphs not belonging in that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of ). We determine these sets for 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 and we prove that there are exactly . Finally, we prove that each obstruction of has at most vertices. [Copyright &y& Elsevier]