summary: For every positive integer k, we define the k-treedepth as the largest graph parameter td_k satisfying (i) td_k(∅)=0; (ii) td_k(G) <= 1+ td_k(G-u) for every graph G and every vertex u; and (iii) if G is a (
This implies for k=1 that a minor-closed class of graphs has bounded treedepth if and only if it excludes a path, for k=2 that a minor-closed class of graphs has bounded 2-treedepth if and only if it excludes a ladder (Huynh, Joret, Micek, Seweryn, and Wollan; Combinatorica, 2021), and for large values of k that a minor-closed class of graphs has bounded treewidth if and only if it excludes a grid (Grid-Minor Theorem, Robertson and Seymour; JCTB, 1986).
As a corollary, we obtain the following qualitative strengthening of the Grid-Minor Theorem in the case of bounded-height grids. For all positive integers k, l, every graph that does not contain the k × l grid as a minor has (2k-1)-treedepth at most a function of (k, l).
