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

dmtcs:3139 - Discrete Mathematics & Theoretical Computer Science, January 17, 2018, Vol. 20 no. 1 - https://doi.org/10.23638/DMTCS-20-1-5
Hitting minors, subdivisions, and immersions in tournamentsArticle

Authors: Jean-Florent Raymond ORCID

    The Erdős-Pósa 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ósa 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ósa property in the class of tournaments.

    Comment: Accepted to Discrete Mathematics & Theoretical Computer Science.
    Difference with the previous version: use of the DMTCS article class. For a version with hyperlinks see the previous version

    https://doi.org/10.23638/DMTCS-20-1-5
    Source: arXiv.org:1605.08366
    Volume: Vol. 20 no. 1
    Section: Graph Theory
    Published on: January 17, 2018
    Accepted on: January 11, 2018
    Submitted on: February 13, 2017
    Keywords: Computer Science - Discrete Mathematics, 05C70, G.2.2
    Licence: arXiv.org - Non-exclusive license to distribute

    Share and export

    Consultation statistics

    This page has been seen 883 times.
    This article's PDF has been downloaded 444 times.