Excluded Forest Minors and the Erdős-Pósa Property

Abstract

A classical result of Robertson and Seymour states that the set of graphs containing a fixed planar graph $H$ as a minor has the so-called Erdős-Pósa property; namely, there exists a function $f$ depending only on $H$ such that, for every graph $G$ and every positive integer $k$, the graph $G$ has $k$ vertex-disjoint subgraphs each containing $H$ as a minor, or there exists a subset $X$ of vertices of $G$ with $|X|\le f(k)$ such that $G-X$ has no $H$-minor. While the best function $f$ currently known is exponential in $k$, a $O(k\log k)$ bound is known in the special case where $H$ is a forest. This is a consequence of a theorem of Bienstock, Robertson, Seymour, and Thomas on the pathwidth of graphs with an excluded forest-minor. In this paper we show that the function $f$ can be taken to be linear when $H$ is a forest. This is best possible in the sense that no linear bound is possible if $H$ has a cycle.

v3: referee's comments implemented

References in corpus (1)

• Hitting Diamonds and Growing Cacti

Cited by in corpus (3)

• Erdős-Pósa from ball packing
• A tight Erdős-Pósa function for wheel minors
• Tight bound for the Erdős-Pósa property of tree minors