Linear bound for the treewidth contraction function
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.
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
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.