Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles

DOI10.1002/jgt.21720zbMath1276.05091OpenAlexW2133890691WikidataQ60488440 ScholiaQ60488440MaRDI QIDQ2862553

Neeldhara Misra, Geevarghese Philip, Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh

Publication date: 15 November 2013

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

Full work available at URL: https://doi.org/10.1002/jgt.21720

zbMATH Keywords

Erdös Pósa propertygeneralization of covering and packing cycles

Mathematics Subject Classification ID

Paths and cycles (05C38) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Related Items (4)

An edge variant of the Erdős-Pósa property ⋮ Minors in graphs of large \(\theta_r\)-girth ⋮ Recent techniques and results on the Erdős-Pósa property ⋮ An \(O(\log \mathrm{OPT})\)-approximation for covering and packing minor models of \(\theta _r\)

Cites Work

• Polynomial treewidth forces a large grid-like-minor
• The Erdős-Pósa property for vertex- and edge-disjoint odd cycles in graphs on orientable surfaces
• The Erdös-Pósa property for matroid circuits
• Graph minors. V. Excluding a planar graph
• Graph searching and a min-max theorem for tree-width
• Treewidth. Computations and approximations
• On the solution of linear recurrence equations
• Disjoint cocircuits in matroids with large rank
• The Erdős-Pósa property for long circuits
• Strengthening Erdös-Pósa property for minor-closed graph classes
• On the presence of disjoint subgraphs of a specified type
• On Independent Circuits Contained in a Graph
• The Erdős-Pósa property for odd cycles in highly connected graphs
• The Erdős-Pósa property for odd cycles in graphs of large connectivity

This page was built for publication: Quadratic Upper Bounds on the Erdős-Pósa Property for a Generalization of Packing and Covering Cycles