The planar-minor Erdős–Pósa conjecture with a tight logarithmic bound

Let HH be a fixed planar graph. For a graph GG, let uH(G) u_H(G) be the maximum number of pairwise vertex-disjoint HH-models in GG, and let τH(G)\tau_H(G) be the minimum size of a vertex set XX such that GXG-X has no HH-model. A bounding function is a function ff satisfying

τH(G)f(νH(G))\tau_H(G)\leq f(\nu_H(G))

for every graph GG.

The planar-minor Erdős–Pósa conjecture. There is a constant depending on HH such that

τH(G)=O(νH(G)logνH(G)).\tau_H(G)=O(\nu_H(G)\log \nu_H(G)).

Equivalently, the Erdős–Pósa property for HH-models has a O(klogk)O(k\log k) bounding function. This would be tight up to the constant factor whenever HH has a cycle, matching the known Ω(klogk)\Omega(k\log k) lower bound; for forests, the optimal order is already O(k)O(k).

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.