Hostname: page-component-55f67697df-zpzq9 Total loading time: 0 Render date: 2025-05-10T07:51:43.573Z Has data issue: false hasContentIssue false
  • English
  • Français

Tight bound for the Erdős–Pósa property of tree minors

Part of: Graph theory

Published online by Cambridge University Press:  11 December 2024

Vida Dujmović ,
Gwenaël Joret ,
Piotr Micek  and
Pat Morin
Vida Dujmović
Affiliation:
School of Computer Science and Electrical Engineering, University of Ottawa, Ottawa, Canada
Gwenaël Joret*
Affiliation:
Computer Science Department, Université libre de Bruxelles, Brussels, Belgium
Piotr Micek
Affiliation:
Theoretical Computer Science Department, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków, Poland
Pat Morin
Affiliation:
School of Computer Science, Carleton University, Ottawa, Canada
*
Corresponding author: Gwenaël Joret; Email: [email protected]
Get access Rights & Permissions [Opens in a new window]

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.

Keywords

Graph minorspathwidthErdős–Pósa property

MSC classification

Primary: 05C83: Graph minors
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 34 , Issue 2 , March 2025 , pp. 321 - 325
Check for updates
Copyright
© The Author(s), 2024. Published by Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable

References

Bienstock, D., Robertson, N., Seymour, P. and Thomas, R. (1991) Quickly excluding a forest. J. Comb. Theory, Series B 52 274–283.CrossRefGoogle Scholar
Cames van Batenburg, W., Huynh, T., Joret, G. and Raymond, J. F. (2019) A tight Erdős-Pósa function for planar minors. Adv. Comb. 10.Google Scholar
Chekuri, C. and Chuzhoy, J. (2013) Large-treewidth graph decompositions and applications. In Proceedings of the 45th annual ACM Symposium on Theory of Computing, ACM. pp. 291–300.CrossRefGoogle Scholar
Chekuri, C. and Chuzhoy, J. (2016) Polynomial bounds for the grid-minor theorem. J. ACM 63 40:1–40:65.CrossRefGoogle Scholar
Diestel, R. (1995) Graph minors 1: A short proof of the path-width theorem. Comb. Prob. Comp. 4 27–30.CrossRefGoogle Scholar
Erdős, P. and Pósa, L. (1965) On independent circuits contained in a graph. Canadian J. Math. 17 347–352.CrossRefGoogle Scholar
Fiorini, S., Joret, G. and Wood, D. R. (2013) Excluded forest minors and the Erdős-Pósa property. Comb. Prob. Comp. 22 700–721.CrossRefGoogle Scholar
Robertson, N. and Seymour, P. D. (1983) Graph minors. I. excluding a forest. J. Comb. Theory Series B 35 39–61.CrossRefGoogle Scholar
Robertson, N. and Seymour, P. D. (1986) Graph minors. V. Excluding a planar graph. J. Comb. Theory Series B 41 92–114.CrossRefGoogle Scholar