Linear bound for the treewidth contraction function
Let be integers. Define to be the minimum integer such that every graph with treewidth at least contains pairwise disjoint connected subgraphs , each with , and contracting each of to a vertex produces a minor of with treewidth at least . Proposed bound.
The grid-minor theorem currently gives the weaker bound : a grid can be partitioned into copies of the grid, whose contractions yield a grid. Improving this polynomial bound is posed as an open problem.
References
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
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.