Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles

DOI10.1002/JGT.22911MaRDI QIDQ6047641zbMATH OpenWikidataFDO

Authors Jie Ma, Chunlei Zu

Publication date 9 October 2023

Published in Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2112.14065

zbMATH Keywords

Birmelé-Bondy-Reed conjectureErdős-Pósalong cycle

Mathematics Subject Classification ID

Distance in graphs (05C12) Paths and cycles (05C38)

Abstract: A conjecture of Birmel'e, Bondy and Reed states that for any integer $ellgeq3$, every graph $G$ without two vertex-disjoint cycles of length at least $ell$ contains a set of at most $ell$ vertices which meets all cycles of length at least $ell$. They showed the existence of such a set of at most $2ell+3$ vertices. This was improved by Meierling, Rautenbach and Sasse to $5ell/3+29/2$. Here we present a proof showing that at most $3ell/2+7/2$ vertices suffice.

Recommendations

• A tight Erdős-Pósa function for long cycles
• A tighter Erdős-Pósa function for long cycles
• A unified Erdős-Pósa theorem for constrained cycles
• Erdős-Pósa property of chordless cycles and its applications
• Erdős-Pósa property of chordless cycles and its applications
• The Erdős-Pósa property for odd cycles in graphs of large connectivity
• On a conjecture of Grünbaum on longest cycles
• The Erdős-Pósa property for long circuits
• The Erdös-Pósa property for long circuits
• The Erdős-Pósa property for long circuits

Cites work

• A tight Erdős-Pósa function for long cycles
• A tighter Erdős-Pósa function for long cycles
• Erdős-Pósa from ball packing
• Erdős-Pósa property of chordless cycles and its applications
• Graphs without two vertex-disjoint S-cycles
• scientific article; zbMATH DE number 3243269 (Why is no real title available?)
• In absence of long chordless cycles, large tree-width becomes a local phenomenon
• Long cycles have the Edge-Erdős-Pósa property
• Long cycles through prescribed vertices have the Erdős-Pósa property
• On Independent Circuits Contained in a Graph
• Recent techniques and results on the Erdős-Pósa property
• The Erdös-Pósa property for long circuits
• The Erdős-Pósa property for long circuits

Cited in

(5)

• A tight Erdős-Pósa function for long cycles
• A unified Erdős-Pósa theorem for constrained cycles
• A tighter Erdős-Pósa function for long cycles
• The Erdős-Pósa property for long circuits
• The Erdös-Pósa property for long circuits

This page was built for publication: Towards a conjecture of Birmelé–Bondy–Reed on the Erdős–Pósa property of long cycles

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6047641)