The Erdős-Pósa property for infinite graphs

Abstract

We investigate which classes of infinite graphs have the Erdős-Pósa property (EPP). In addition to the usual EPP, we also consider the following infinite variant of the EPP: a class $\mathcal{G}$ of graphs has the $\hat{I}º$-EPP, where $\hat{I}º$ is an infinite cardinal, if for any graph $\hat{I}“$ there are either $\hat{I}º$ disjoint graphs from $\mathcal{G}$ in $\hat{I}“$ or there is a set $X$ of vertices of $\hat{I}“$ of size less than $\hat{I}º$ such that $\hat{I}“-X$ contains no graph from $\mathcal{G}$. In particular, we study the ($\hat{I}º$-)EPP for classes consisting of a single infinite graph $G$. We obtain positive results when the set of induced subgraphs of $G$ is labelled well-quasi-ordered, and negative results when $G$ is not a proper subgraph of itself (both results require some additional conditions). As a corollary, we obtain that every graph which does not contain a path of length $n$ for some $n\in \mathbb{N}$ has the EPP and the $\hat{I}º$-EPP. Furthermore, we show that the class of all subdivisions of any tree $T$ has the $\hat{I}º$-EPP for every uncountable cardinal $\hat{I}º$, and if $T$ is rayless, also the ${\aleph }_0$-EPP and the EPP.

25 pages, 5 figures