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

About 9 years old · traced to

Let WtW_t denote the wheel on t+1t+1 vertices, and let t≥3t\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:N→Ng:\mathbb{N}\to\mathbb{N} such that, for every integer t≥3t\geq 3, wheel models in GG have the Erdős–Pósa property with bounding function

cklog⁡k+g(t)k.c k\log k+g(t)k.

The paper proves an O(klog⁡k)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.

References

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.