Forbidden graphs for tree-depth

Zdeněk Dvořák, Archontia C. Giannopoulou, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


For every kge. 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 set of graphs not belonging in Gk that are minimal with respect to the minor/subgraph/induced subgraph relation (obstructions of Gk). 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 Gk and we prove that there are exactly 1222k-1-k(1+22k-1-k). Finally, we prove that each obstruction of Gk has at most 22k-1 vertices.

Original languageEnglish (US)
Pages (from-to)969-979
Number of pages11
JournalEuropean Journal of Combinatorics
Issue number5
StatePublished - Jul 2012

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Forbidden graphs for tree-depth'. Together they form a unique fingerprint.

Cite this