The Erdős-Pósa property for infinite graphs
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913571726688256 |
|---|---|
| author | Krill, Thilo |
| author_facet | Krill, Thilo |
| contents | 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 $κ$-EPP, where $κ$ is an infinite cardinal, if for any graph $Γ$ there are either $κ$ disjoint graphs from $\mathcal{G}$ in $Γ$ or there is a set $X$ of vertices of $Γ$ of size less than $κ$ such that $Γ- X$ contains no graph from $\mathcal{G}$. In particular, we study the ($κ$-)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 $κ$-EPP. Furthermore, we show that the class of all subdivisions of any tree $T$ has the $κ$-EPP for every uncountable cardinal $κ$, and if $T$ is rayless, also the $\aleph_0$-EPP and the EPP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_02561 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | The Erdős-Pósa property for infinite graphs Krill, Thilo Combinatorics 05C63 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 $κ$-EPP, where $κ$ is an infinite cardinal, if for any graph $Γ$ there are either $κ$ disjoint graphs from $\mathcal{G}$ in $Γ$ or there is a set $X$ of vertices of $Γ$ of size less than $κ$ such that $Γ- X$ contains no graph from $\mathcal{G}$. In particular, we study the ($κ$-)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 $κ$-EPP. Furthermore, we show that the class of all subdivisions of any tree $T$ has the $κ$-EPP for every uncountable cardinal $κ$, and if $T$ is rayless, also the $\aleph_0$-EPP and the EPP. |
| title | The Erdős-Pósa property for infinite graphs |
| topic | Combinatorics 05C63 |
| url | https://arxiv.org/abs/2411.02561 |