Obstructions for Tree-depth

Archontia C. Giannopoulou, Dimitrios M. Thilikos

Research output: Contribution to journalArticlepeer-review


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

Original languageEnglish (US)
Pages (from-to)249-253
Number of pages5
JournalElectronic Notes in Discrete Mathematics
StatePublished - Aug 1 2009


  • graph enumeration
  • Graph minors
  • obstructions
  • tree depth
  • vertex rankings

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Obstructions for Tree-depth'. Together they form a unique fingerprint.

Cite this