Long cycles have the edge-Erd Hos-P 'osa property

2016/07/07 by Henning Bruhn, Bruhn, Henning, Matthias Heinlein +3
Computer Science · Mathematics · #Combinatorics (math.CO) #Computability, Logic, AI Algorithms #FOS: Mathematics #Limits and Structures in Graph Theory #semigroups and automata theory

paper · pdf · doi:10.48550/arxiv.1607.01903

openalex publication_date 2016/07/07 · openalex created_date 2022/10/01 · openalex updated_date 2026/07/28

Abstract

We prove that the set of long cycles has the edge-Erd Hos-P 'osa property:\nfor every fixed integer \ℓ\≥ 3 and every k\∈\ℕ, every graph G\neither contains k edge-disjoint cycles of length at least \ℓ (long\ncycles) or an edge set X of size O(k²\log k + \ℓ k) such that G-X does\nnot contain any long cycle. This answers a question of Birmel 'e, Bondy, and\nReed (Combinatorica 27 (2007), 135--145).\n

Related

• A tight Erdős-Pósa function for long cycles
• Long cycles through prescribed vertices have the Erdős-Pósa property
• Towards a conjecture of Birmelé-Bondy-Reed on the Erdős-Pósa property of long cycles
• A tighter Erdös-Pósa function for long cycles
• Even A-cycles have the edge-Erdős-Pósa property