Back to Search
Start Over
On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments
- Source :
- Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (April 5, 2022) dmtcs:7099
- Publication Year :
- 2021
-
Abstract
- We consider the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments. We prove that for every simple digraph $H$, $k\in \mathbb{N}$, and tournament $T$, the following statements hold: (i) If in $T$ one cannot find $k$ arc-disjoint immersion copies of $H$, then there exists a set of $\mathcal{O}_H(k^3)$ arcs that intersects all immersion copies of $H$ in $T$. (ii) If in $T$ one cannot find $k$ vertex-disjoint topological minor copies of $H$, then there exists a set of $\mathcal{O}_H(k\log k)$ vertices that intersects all topological minor copies of $H$ in $T$. This improves the results of Raymond [DMTCS '18], who proved similar statements under the assumption that $H$ is strongly connected.<br />Comment: 15 pages, 1 figure
- Subjects :
- Mathematics - Combinatorics
05C70
G.2.2
Subjects
Details
- Database :
- arXiv
- Journal :
- Discrete Mathematics & Theoretical Computer Science, vol. 24, no. 1, Graph Theory (April 5, 2022) dmtcs:7099
- Publication Type :
- Report
- Accession number :
- edsarx.2101.06732
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.46298/dmtcs.7099