Raymond, Jean-Florent - Hitting minors, subdivisions, and immersions in tournaments

dmtcs:4212 - Discrete Mathematics & Theoretical Computer Science, January 17, 2018, Vol. 20 no. 1
Hitting minors, subdivisions, and immersions in tournaments

Authors: Raymond, Jean-Florent

The Erdős-P\'osa property relates parameters of covering and packing of combinatorial structures and has been mostly studied in the setting of undirected graphs. In this note, we use results of Chudnovsky, Fradkin, Kim, and Seymour to show that, for every directed graph $H$ (resp. strongly-connected directed graph $H$), the class of directed graphs that contain $H$ as a strong minor (resp. butterfly minor, topological minor) has the vertex-Erdős-P\'osa property in the class of tournaments. We also prove that if $H$ is a strongly-connected directed graph, the class of directed graphs containing $H$ as an immersion has the edge-Erdős-P\'osa property in the class of tournaments.


Source : oai:arXiv.org:1605.08366
DOI : 10.23638/DMTCS-20-1-5
Volume: Vol. 20 no. 1
Section: Graph Theory
Published on: January 17, 2018
Submitted on: February 13, 2017
Keywords: Computer Science - Discrete Mathematics,05C70,G.2.2


Share

Consultation statistics

This page has been seen 159 times.
This article's PDF has been downloaded 56 times.