{"id":"arxiv/2604.05690","url":"https://arxiv.org/abs/2604.05690","tags":["math.CO","cs.DM"],"score":0,"title":"Tree-partitions and small-spread tree-decompositions","domain":"math.CO","source":"arxiv","authors":["Marc Distel","Neel Kaul","Raj Kaul","David R. Wood"],"reviews":0,"subject":"math.CO","summary":"Tree-decompositions and treewidth are of fundamental importance in structural and algorithmic graph theory. The \"spread\" of a tree-decomposition is the minimum integer $s$ such that every vertex lies in at most $s$ bags. A tree-decomposition is \"domino\" if it has spread 2, which is the smallest interesting value of spread. So that spread 1 becomes interesting, one can relax the definition of tree-decomposition to \"tree-partition\", which allows the endpoints of each edge to be in the same bag or adjacent bags, while demanding that each vertex appears in exactly one bag. Ding and Oporowski…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-07","reactions":{}}