no. 15 · Monday 16 November 2026
Tree-partitions of graphs with bounded tree-depth
Abstract
A tree-partition of a graph $G$ is a partition of $V(G)$ such that identifying the vertices in each part gives a tree. It is known that every graph with treewidth $k$ and maximum degree $Δ(G)$ has a tree-partition in which each part has size $O(k\cdotΔ(G))$. In this paper, we study tree-partitions of graphs with bounded tree-depth, a stronger parameter than treewidth, with an additional property for the tree $T$ indexing the tree-partition. We prove that every connected graph with tree-depth $h$ admits a $T$-partition for some tree $T$ with $\operatorname{rad}(T)\leq h-1$ and with width at most $\mathrm{max}\{1, (4h-10)Δ(G)+1\}$.
- fields
- Combinatorics