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

1 Citation (Scopus)

Abstract

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
Volume32
Issue number3
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes

Keywords

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

Cite this

Aboulker, P., Fiorini, S., Huynh, T., Joret, G., Raymond, J. F., & Sau, I. (2018). A tight Erdős–Pósa function for wheel minors. SIAM Journal on Discrete Mathematics, 32(3), 2302-2312. https://doi.org/10.1137/17M1153169