The treewidth packing conjecture with a logarithmic bound

For a graph GG, let r,k1r,k\geq 1 be integers, and let f:NNf:\mathbb{N}\to\mathbb{N} be a function.

Treewidth packing conjecture. There is a function f:NNf:\mathbb{N}\to\mathbb{N} such that every graph GG with

tw(G)f(r)klog(k+1)\operatorname{tw}(G)\geq f(r)\,k\log(k+1)

has kk vertex-disjoint subgraphs G1,,GkG_1,\dots,G_k, each satisfying

tw(Gi)r.\operatorname{tw}(G_i)\geq r.

This would improve the logarithmic exponent in the polynomial Grid Theorem and is suggested as a possible route toward the tight Erdős–Pósa bound for planar-minor models. The source presents it as a natural side conjecture and gives no resolution.

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.