Trade-off between spread and width for tree decompositions

Abstract

The spread of a vertex $v$ in a tree decomposition is the number of bags that contain $v$. We study the trade-off between spread and width in tree decompositions, answering every open question from Wood [arXiv:2509.01140]. First, Wood asked for the infimum of $c>0$ such that there exists $c^{\prime }$ such that each graph $G$ has a tree decomposition of width $c\cdot tw(G)$ in which each vertex $v$ has spread at most $c^{\prime }(d(v)+1)$. We show that the answer is $3$. Second, we prove a conjecture of Wood, stating that every tree-decomposition of the $(n\times n)$-grid with width $n$ has a vertex with spread $\Omega (n)$. Finally, we answer the last question of Wood by showing that near-optimal average spread can be achieved simultaneously with width $O(tw(G))$.

This new version includes new results of from Sergey Norin and Neil Rahman