Paperlane

no. 15 · Monday 16 November 2026

Tree-partitions of graphs with bounded tree-depth

Rong Chen and Huayue Liu

math.CO · v2

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
pdf ↗ page arXiv:2608.12723 ↗