Back to Search Start Over

On the Erdős-Pósa property for immersions and topological minors in tournaments.

Authors :
Bozyk, Łukasz
Pilipczuk, Michał
Source :
Discrete Mathematics & Theoretical Computer Science (DMTCS). 2022, Vol. 24 Issue 1, p1-16. 16p.
Publication Year :
2022

Abstract

We consider the Erdős-Pósa property for immersions and topological minors in tournaments. We prove that for every simple digraph H, k 2 N, and tournament T, the following statements hold: • If in T one cannot find k arc-disjoint immersion copies of H, then there exists a set of OH(k3) arcs that intersects all immersion copies of H in T. • If in T one cannot find k vertex-disjoint topological minor copies of H, then there exists a set of OH(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. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
13658050
Volume :
24
Issue :
1
Database :
Academic Search Index
Journal :
Discrete Mathematics & Theoretical Computer Science (DMTCS)
Publication Type :
Academic Journal
Accession number :
157096834