Rong Chen

Tree-partitions of graphs with bounded tree-depth

Wood~ recently showed that every graph $G$ of pathwidth $h$ and $\Delta(G)\ge1$ admits a $T$-partition of width at most $4(h+1)^2\Delta(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...