2025/01/20 by Clément Rambaud, Rambaud, Clément
Computer Science · Mathematics · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.2501.11617
48 pages, 15 figures, revision
arxiv created 2026/07/31 · arxiv updated 2026/08/03
For every positive integer k, we define the k-treedepth as the largest graph parameter tdk satisfying (i) tdk(∅)=0; (ii) tdk(G) ≤ 1+ tdk(G-u) for every graph G and every vertex u ∈ V(G); and (iii) if G is a (<k)-clique-sum of G1 and G2, then tdk(G) ≤ max \tdk(G1),tdk(G2)\, for all graphs G1,G2. This parameter coincides with treedepth if k=1, and with treewidth plus 1 if k ≥ |V(G)|. We prove that for every positive integer k, a class of graphs C has bounded k-treedepth if and only if there is a positive integer ℓ such that for every tree T on k vertices, no graph in C contains T \square P_ℓ as a minor. 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 as a minor 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, ℓ, every graph that does not contain the k × ℓ grid as a minor has (2k-1)-treedepth at most a function of k and ℓ.