| Autor: |
Łukasz Bożyk, Michał Pilipczuk |
| Jazyk: |
angličtina |
| Rok vydání: |
2022 |
| Předmět: |
|
| Zdroj: |
Discrete Mathematics & Theoretical Computer Science, Vol vol. 24, no. 1, Iss Graph Theory (2022) |
| Druh dokumentu: |
article |
| ISSN: |
1365-8050 |
| DOI: |
10.46298/dmtcs.7099 |
| Popis: |
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. |
| Databáze: |
Directory of Open Access Journals |
| Externí odkaz: |
|
