TY - JOUR

T1 - Forbidden graphs for tree-depth

AU - Dvořák, Zdeněk

AU - Giannopoulou, Archontia C.

AU - Thilikos, Dimitrios M.

PY - 2012/7

Y1 - 2012/7

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=84856958653&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84856958653&partnerID=8YFLogxK

U2 - 10.1016/j.ejc.2011.09.014

DO - 10.1016/j.ejc.2011.09.014

M3 - Article

AN - SCOPUS:84856958653

SN - 0195-6698

VL - 33

SP - 969

EP - 979

JO - European Journal of Combinatorics

JF - European Journal of Combinatorics

IS - 5

ER -