Directed cycles have the edge-Erd\H os-Pósa property

2018/02/14 by Matthias Heinlein, Heinlein, Matthias, Arthur Ulmer +1
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.1802.05026

openalex publication_date 2018/02/14 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In this short note we prove that for every k∈ ℕ there is a t_k∈ℕ such that for every digraph G there are either k edge-disjoint directed cycles in G or a set X of at most t_k edges such that G-X contains no directed cycle.

Related

• Long cycles have the edge-Erd Hos-P 'osa property
• The Erdos-Posa Property for Directed Graphs
• Even A-cycles have the edge-Erdős-Pósa property
• A half-integral Erdős-Pósa theorem for directed odd cycles
• Long cycles through prescribed vertices have the Erdős-Pósa property