The planar-minor Erdős–Pósa conjecture with a tight logarithmic bound
The planar-minor Erdős–Pósa conjecture with a tight logarithmic bound
Let be a fixed planar graph. For a graph , let be the maximum number of pairwise vertex-disjoint -models in , and let be the minimum size of a vertex set such that has no -model. A bounding function is a function satisfying
for every graph .
The planar-minor Erdős–Pósa conjecture. There is a constant depending on such that
Equivalently, the Erdős–Pósa property for -models has a bounding function. This would be tight up to the constant factor whenever has a cycle, matching the known lower bound; for forests, the optimal order is already .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.