Spread versus width conjecture for grid tree decompositions
Spread versus width conjecture for grid tree decompositions
Let be integers, and let denote the additional width parameter in a tree-decomposition of the -grid whose width is . The spread versus width conjecture. There is a constant such that every such tree-decomposition has a vertex with spread at least
This would strengthen Wood's conjecture that every tree-decomposition of the -grid with width has a vertex with spread , 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
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.