{"id":"arxiv/2608.12723","url":"https://arxiv.org/abs/2608.12723","tags":["math.CO"],"score":0,"title":"Tree-partitions of graphs with bounded tree-depth","domain":"math.CO","source":"arxiv","authors":["Rong Chen","Huayue Liu"],"reviews":0,"subject":"math.CO","summary":"Wood~ recently showed that every graph $G$ of pathwidth $h$ and $Δ(G)\\ge1$ admits a $T$-partition of width at most $4(h+1)^2Δ(G)$ for some tree $T$ with $pw(T)\\leq2h+1$. In this paper, we establish an analogous result for tree-depth, which is a stronger parameter than pathwidth. We prove that every connected graph with tree-depth $h$ admits a $T$-partition of width at most $\\mathrm{max}\\{1, (4h-10)Δ(G)+1\\}$ for some tree $T$ with $\\operatorname{rad}(T)\\leq h-1$.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-13","reactions":{}}