## Abstract

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