Tree-partitions of graphs with bounded tree-depth

Abstract

Wood~ recently showed that every graph $G$ of pathwidth $h$ and $\Delta (G)\ge 1$ admits a $T$-partition of width at most $4(h+1{)}^2\Delta (G)$ for some tree $T$ with $pw(T)\le 2h+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 $\max \{1,(4h-10)\Delta (G)+1\}$ for some tree $T$ with $\mathrm{rad}(T)\le h-1$.