Tight bound for the Erdős–Pósa property of tree minors
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 fast-growing function $f(t)$ . Moreover, our proof is short and simple.
Authors
- Vida Dujmović (ORCID: https://orcid.org/0000-0001-7250-0600)
- Gwenaël Joret (ORCID: https://orcid.org/0000-0002-7157-6694)
- Pat Morin (ORCID: https://orcid.org/0000-0003-0471-4118)
- Piotr Micek (ORCID: https://orcid.org/0000-0001-9796-5375)
Institutions
- Jagiellonian University (PL)
- Université Libre de Bruxelles (BE)
- University of Ottawa (CA)
- Carleton University (CA)
Publication Details
- Journal
- Combinatorics Probability Computing
- Published
- 2024-12-11
- DOI
- https://doi.org/10.1017/s0963548324000415
- Citations
- 1
- Primary Topic
- Advanced Graph Theory Research
- Type
- article
- Field-Weighted Citation Impact
- 0.36
Funders
- University of Ottawa
- Fonds De La Recherche Scientifique - FNRS
- Natural Sciences and Engineering Research Council of Canada