Tree decompositions with small width, spread, order and degree
This solves a structural graph theory problem for researchers in algorithms and combinatorics, providing efficient decompositions with practical implications.
The paper tackles the problem of constructing tree-decompositions for graphs with small treewidth, achieving a linear bound of width at most 72k+1, with additional constraints on vertex appearances, bag count, and tree degree, improving prior exponential bounds.
Tree-decompositions of graphs are of fundamental importance in structural and algorithmic graph theory. The main property of tree-decompositions is the width (the maximum size of a bag $-1$). We show that every graph has a tree-decomposition with near-optimal width, plus several additional properties of interest. In particular every graph $G$ with treewidth at most $k$ has a tree-decomposition with width at most $72k+1$, where each vertex $v$ appears in at most $\text{deg}_G(v)+1$ bags, the number of bags is at most $\max\{\frac{|V(G)|}{2k},1\}$, and the tree indexing the decomposition has maximum degree at most 12. This improves exponential bounds to linear in a result of Ding and Oporowski [1995], and establishes a conjecture of theirs in a strong sense.