Łukasz Bożyk ; Michał Pilipczuk - On the Erdős-Pósa property for immersions and topological minors in tournaments

dmtcs:7099 - Discrete Mathematics & Theoretical Computer Science, April 5, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.7099
On the Erdős-Pósa property for immersions and topological minors in tournamentsArticle

Authors: Łukasz Bożyk ; Michał Pilipczuk

We consider the Erdős-Pósa 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


Volume: vol. 24, no. 1
Section: Graph Theory
Published on: April 5, 2022
Accepted on: March 9, 2022
Submitted on: January 19, 2021
Keywords: Mathematics - Combinatorics, 05C70, G.2.2
Funding:
    Source : OpenAIRE Graph
  • Technology transfer between modern algorithmic paradigms; Funder: European Commission; Code: 677651
  • Cuts and decompositions: algorithms and combinatorial properties; Funder: European Commission; Code: 714704

Consultation statistics

This page has been seen 1263 times.
This article's PDF has been downloaded 1076 times.