{
  "id": "2403.06370",
  "version": "v1",
  "published": "2024-03-11T01:48:39.000Z",
  "updated": "2024-03-11T01:48:39.000Z",
  "title": "Tight bound for the Erdős-Pósa property of tree minors",
  "authors": [
    "Vida Dujmović",
    "Gwenaël Joret",
    "Piotr Micek",
    "Pat Morin"
  ],
  "categories": [
    "math.CO",
    "cs.DM"
  ],
  "abstract": "Let $T$ be a tree on $t$ vertices. We prove that for every positive integer $k$ and every graph $G$, either $G$ contains $k$ pairwise vertex-disjoint subgraphs each having a $T$ minor, or there exists a set $X$ of at most $t(k-1)$ vertices of $G$ such that $G-X$ has no $T$ minor. The bound on the size of $X$ is best possible and improves on an earlier $f(t)k$ bound proved by Fiorini, Joret, and Wood (2013) with some very fast growing function $f(t)$. Moreover, our proof is very short and simple.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2024-03-11T01:48:39.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "erdős-pósa property",
      "tree minors",
      "tight bound",
      "fast growing function",
      "pairwise vertex-disjoint subgraphs"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}