A tight Erdős–Pósa function for wheel minors

Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean Florent Raymond, Ignasi Sau

Research output: Contribution to journalArticleResearchpeer-review

3 Citations (Scopus)


Let Wt denote the wheel on t + 1 vertices. We prove that for every integer t ≥ 3 there is a constant c = c(t) such that for every integer k ≥ 1 and every graph G, either G has k vertex-disjoint subgraphs each containing Wt as a minor, or there is a subset X of at most ck log k vertices such that G - X has no Wt minor. This is best possible, up to the value of c. We conjecture that the result remains true more generally if we replace Wt with any fixed planar graph H.

Original languageEnglish
Pages (from-to)2302-2312
Number of pages11
JournalSIAM Journal on Discrete Mathematics
Issue number3
Publication statusPublished - 1 Jan 2018
Externally publishedYes


  • Covering
  • Erdos--Pósa property
  • Packing
  • Wheel minors

Cite this