A tight Erdős-Pósa function for planar minors

DOI10.1137/1.9781611975482.90MaRDI QIDQ5236274zbMATH OpenOpenAlexFDO

Authors Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond

Publication date 15 October 2019

Published in Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1137/1.9781611975482.90

zbMATH Keywords

approximation algorithm for packing subgraphs

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph minors (05C83)

Recommendations

• A tight Erdős-Pósa function for planar minors
• Strengthening Erdős -- Pósa property for minor-closed graph classes
• Excluded Forest Minors and the Erdős–Pósa Property
• A tight Erdős-Pósa function for wheel minors
• Polynomial gap extensions of the Erdős-Pósa theorem

Cited in

(20)

• An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)
• Packing and covering balls in graphs excluding a minor
• Jones' conjecture in subcubic graphs
• An \(O(\log \mathrm{OPT})\)-approximation for covering/packing minor models of \(\theta _{r}\)
• Quadratic upper bounds on the Erdős--Pósa property for a generalization of packing and covering cycles
• Strengthening Erdős -- Pósa property for minor-closed graph classes
• scientific article; zbMATH DE number 64356 (Why is no real title available?)
• The Erdős-Pósa property for clique minors in highly connected graphs
• Erdős-Pósa property for labeled minors: 2-connected minors
• Bridge-depth characterizes which minor-closed structural parameterizations of vertex cover admit a polynomial kernel
• A tight Erdős-Pósa function for planar minors
• Erdős-Pósa from ball packing
• A tight Erdős-Pósa function for wheel minors
• Excluded Forest Minors and the Erdős–Pósa Property
• Polynomial gap extensions of the Erdős-Pósa theorem
• Packing topological minors half‐integrally
• On the Erdős–Pósa Property for Long Holes in \(\boldsymbol{C_4}\)-Free Graphs
• A constant-factor approximation for weighted bond cover
• Bridge-depth characterizes which structural parameterizations of vertex cover admit a polynomial kernel
• Delineating half-integrality of the Erdős-Pósa property for minors: the case of surfaces

This page was built for publication: A tight Erdős-Pósa function for planar minors

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