Erdös--Pósa from Ball Packing

DOI10.1137/19M1309225zbMath1450.05045arXiv1912.07965OpenAlexW2994727147MaRDI QIDQ5130570

Gwenaël Joret, Arthur Ulmer, Wouter Cames van Batenburg

Publication date: 28 October 2020

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

coveringcyclepackingErdős-Pósa theorem

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83) Distance in graphs (05C12)

Related Items (1)

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

Cites Work

• Unnamed Item
• An edge variant of the Erdős-Pósa property
• Dense minors in graphs of large girth
• Disjoint cycles intersecting a set of vertices
• Graph minors. V. Excluding a planar graph
• \(K_4\)-expansions have the edge-Erdős-Pósa property
• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• A tight Erdős-Pósa function for long cycles
• The extremal function for disconnected minors
• Recent techniques and results on the Erdős-Pósa property
• Long cycles have the Edge-Erdős-Pósa property
• The Erdős-Pósa property for long circuits
• A Tighter Erdős-Pósa Function for Long Cycles
• On the presence of disjoint subgraphs of a specified type
• Frames, $A$-Paths, and the Erdös--Pósa Property
• Minors in graphs of large girth
• A tight Erdős-Pósa function for planar minors
• On Independent Circuits Contained in a Graph
• Excluded Forest Minors and the Erdős–Pósa Property

This page was built for publication: Erdös--Pósa from Ball Packing