{
  "id": "2501.11617",
  "version": "v1",
  "published": "2025-01-20T17:29:53.000Z",
  "updated": "2025-01-20T17:29:53.000Z",
  "title": "Excluding a rectangular grid",
  "authors": [
    "Clément Rambaud"
  ],
  "comment": "44 pages, 15 figures",
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "For every positive integer $k$, we define the $k$-treedepth as the largest graph parameter $\\mathrm{td}_k$ satisfying (i) $\\mathrm{td}_k(\\emptyset)=0$; (ii) $\\mathrm{td}_k(G) \\leq 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) \\leq \\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 \\geq |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, \\ell)$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2025-01-20T17:29:53.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "rectangular grid",
      "positive integer",
      "minor-closed class",
      "grid-minor theorem",
      "largest graph parameter"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 44,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}