Erdős–Pósa O(k log k) bound for planar H-minors

Conjecture 1.2 · arXiv:1710.06282

arXiv Conjecture high confidence— first stated 2018-07-05

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

Status solved high confidence

Conjecture 1.2 was resolved by Cames van Batenburg, Huynh, Joret, and Raymond in arXiv:1807.04969, submitted just eight days after the journal publication date of the source paper. They prove that for every planar graph H, the Erdős-Pósa property holds for H-models with a c(H)·k log k bounding function, which is best possible up to the constant for any H containing a cycle. The result was published in Advances in Combinatorics in 2019, fully settling the growth rate of the Erdős-Pósa function for all planar graphs H.

Cited literature (1)

proof A tight Erdős-Pósa function for planar minors (2018)

Wouter Cames van Batenburg, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond · Advances in Combinatorics (2019) · arXiv:1807.04969

Proves the full conjecture: for every planar graph H, every graph G either contains k vertex-disjoint H-models or a hitting set of at most c(H)·k log k vertices, establishing the tight Θ(k log k) growth rate.

Reviewer notes. The conjecture was settled by arXiv:1807.04969 (Cames van Batenburg, Huynh, Joret, Raymond), submitted July 13 2018 — eight days after the journal publication date of the source paper (the source arXiv preprint 1710.06282 appeared in October 2017). Both internal references are false positives unrelated to the Erdős-Pósa topic.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Conjecture. For every planar graph $H$, the Erdős-Pósa property holds for $H$-models with a $O(k \log k)$ bounding function.

Context

Chekuri and Chuzhoy established a $O(k \log^c k)$ bounding function for planar $H$-models with $c$ at least a double-digit integer; their approach necessarily yields $c \geq 2$. Since a $\Omega(k \log k)$ lower bound already holds for any planar $H$ containing a cycle, proving this conjecture would completely settle the growth rate of the Erdős-Pósa function for all planar graphs $H$. The paper proves the conjecture for $H = W_t$ (wheels) as its main result.

Source paper

A tight Erdős-Pósa function for wheel minors
Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond, Ignasi Sau · 2018-07-05
https://arxiv.org/abs/1710.06282 PDF source