Skip to main contentSkip to search
Episciences
Open Access Journals
Sign in(new window)
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Discrete Mathematics & Theoretical Computer Science logo
Discrete Mathematics & Theoretical Computer Science
Sign in(new window)
Articles & Issues
All articlesAll accepted articlesAll volumesLast volumeSectionsSpecial issuesAuthors
About
The journalIndexing
Boards
Publish
For authorsEthical charter
Submit
Discrete Mathematics & Theoretical Computer Science logo
Contact
|
Credits
eISSN 1365-8050
|
RSS
|
Atom
Episciences
Documentation
|
Acknowledgements
|
Publishing policy
Accessibility: non-compliant
|
Legal mentions
|
Privacy statement
|
Terms of use
  1. Home > Articles & Issues >
  2. Articles >
  3. On the Erd\H{o}s-P\' ...
Article

On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments

Łukasz Bożyk, Michał Pilipczuk
Download article
Open on arXiv
Submitted on
January 19, 2021
Accepted on
March 9, 2022
Published on
April 5, 2022
Last modified on
March 31, 2025
Volume 24
vol. 24:1
Graph Theory
DOI
10.46298/dmtcs.7099
License
arXiv.org - Non-exclusive license to distribute
Cuts and decompositions: algorithms and combinatorial properties
Indicators
1455
Views
1250
Downloads

On the Erd\H{o}s-P\'osa property for immersions and topological minors in tournaments

Łukasz Bożyk, Michał Pilipczuk
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. Comment: 15 pages, 1 figure
Keywords
  • Mathematics - Combinatorics
  • 05C70
  • G.2.2
Mathematics Subject Classification 2020
  • 05C20 - Directed graphs (digraphs), tournaments
  • 05C70 - Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
  • 05C83 - Graph minors
Preview
Loading PDF preview...