Abstract
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 language | English (US) |
---|---|
Pages (from-to) | 249-253 |
Number of pages | 5 |
Journal | Electronic Notes in Discrete Mathematics |
Volume | 34 |
DOIs | |
State | Published - Aug 1 2009 |
Keywords
- graph enumeration
- Graph minors
- obstructions
- tree depth
- vertex rankings
ASJC Scopus subject areas
- Discrete Mathematics and Combinatorics
- Applied Mathematics