{"id":"arxiv/2607.27601","url":"https://arxiv.org/abs/2607.27601","tags":["math.CO","cs.DM"],"score":0,"title":"Optimal tree-decompositions with bags of bounded pathwidth","domain":"math.CO","source":"arxiv","authors":["Kevin Hendrey","Robert Hickingbotham","Jędrzej Hodor","David R. Wood"],"reviews":0,"subject":"math.CO","summary":"We show that every planar graph has a tree-decomposition with optimal width such that the subgraph induced by each bag has pathwidth at most 3. This bound is best possible, and for tree-decompositions that satisfy a certain minimality condition, we in fact give a precise description of the possible structures in each bag. Moreover, we show that the union of any $k$ bags has pathwidth $O(k)$. We also show that graphs excluding a fixed double-apex-forest minor have a tree-decomposition with optimal width such that the subgraph induced by each bag has bounded pathwidth. This includes graphs…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-30","reactions":{}}