Linear bound for the treewidth contraction function

Let p,q1p,q\geqslant 1 be integers. Define (p,q)\ell(p,q) to be the minimum integer such that every graph GG with treewidth at least (p,q)\ell(p,q) contains pairwise disjoint connected subgraphs G1,G2,,GnG_1,G_2,\dots,G_n, each with tw(Gi)p\operatorname{tw}(G_i)\geqslant p, and contracting each of G1,,GnG_1,\dots,G_n to a vertex produces a minor of GG with treewidth at least qq. Proposed bound.

(p,q)O(pq).\ell(p,q)\leqslant O^\ast(pq).

The grid-minor theorem currently gives the weaker bound (p,q)O((pq)9)\ell(p,q)\leqslant O^\ast((pq)^9): a (pq)×(pq)(pq)\times(pq) grid can be partitioned into q2q^2 copies of the p×pp\times p grid, whose contractions yield a q×qq\times q grid. Improving this polynomial bound is posed as an open problem.

Sources & referencesView supporting material

Primary source

Kevin Hendrey and David R. Wood, “Polynomial Bounds in the Apex Minor Theorem”, arXiv:2503.04228 (2025).

Additional references

2 papers in this index state this conjecture (2024–2025). The statement above is taken from the most recent of them; the others are arXiv:2402.17255.

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.