Spread versus width conjecture for grid tree decompositions

Let mn1m\geq n\geq 1 be integers, and let aa denote the additional width parameter in a tree-decomposition of the (n×m)(n\times m)-grid whose width is n+an+a. The spread versus width conjecture. There is a constant δ>0\delta>0 such that every such tree-decomposition has a vertex with spread at least

δ(n/a).\delta (n/a).

This would strengthen Wood's conjecture that every tree-decomposition of the (n×n)(n\times n)-grid with width nn has a vertex with spread Ω(n)\Omega(n), and would be best possible up to the multiplicative constant. The conjecture concerns the trade-off between the width and spread of tree decompositions; its status is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Hans L. Bodlaender and Carla Groenland, “Trade-off between spread and width for tree decompositions”, arXiv:2601.04040 (2026).

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.