The uniform Erdős–Pósa conjecture for wheel models

Let WtW_t denote the wheel on t+1t+1 vertices, and let t3t\geq 3. For a graph GG, a wheel model is a model of WtW_t in GG.

Uniform wheel-model Erdős–Pósa conjecture. There are a constant c>0c>0 and a function g:NNg:\mathbb{N}\to\mathbb{N} such that, for every integer t3t\geq 3, wheel models in GG have the Erdős–Pósa property with bounding function

cklogk+g(t)k.c k\log k+g(t)k.

The paper proves an O(klogk)O(k\log k) bound for each fixed wheel, while this conjecture asks that the coefficient of the logarithmic term be independent of the wheel size tt. It is motivated by the analogous result for cycle models and remains open in the source.

Sources & referencesView supporting material

Primary source

Pierre Aboulker, Samuel Fiorini, Tony Huynh, Gwenaël Joret, Jean-Florent Raymond and Ignasi Sau, “A tight Erdős-Pósa function for wheel minors”, arXiv:1710.06282 (2018).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.