Excluding a rectangular grid

Abstract

For every positive integer $k$, we define the $k$-treedepth as the largest graph parameter ${\mathrm{td}}_k$ satisfying (i) ${\mathrm{td}}_k(\varnothing )=0$; (ii) ${\mathrm{td}}_k(G)\le 1+{\mathrm{td}}_k(G-u)$ for every graph $G$ and every vertex $u\in V(G)$; and (iii) if $G$ is a $(<k)$-clique-sum of $G_1$ and $G_2$, then ${\mathrm{td}}_k(G)\le \max \{{\mathrm{td}}_k(G_1),{\mathrm{td}}_k(G_2)\}$, for all graphs $G_1,G_2$. This parameter coincides with treedepth if $k=1$, and with treewidth plus $1$ if $k\ge |V(G)|$. We prove that for every positive integer $k$, a class of graphs $\mathcal{C}$ has bounded $k$-treedepth if and only if there is a positive integer $\ell$ such that for every tree $T$ on $k$ vertices, no graph in $\mathcal{C}$ contains $T\square P_{\ell }$ 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,\ell$, every graph that does not contain the $k\times \ell$ grid as a minor has $(2k-1)$-treedepth at most a function of $k$ and $\ell$.

arXiv comment48 pages, 15 figures, revision