On tree-partition-width

A tree-partition of a graph G is a proper partition of its vertex set into ‘bags’, such that identifying the vertices in each bag produces a forest. The width of a tree-partition is the maximum number of vertices in a bag. The tree-partition-width of G is the minimum width of a tree-partition of G . An anonymous referee of the paper [Guoli Ding, Bogdan Oporowski, Some results on tree decomposition of graphs, J. Graph Theory 20 (4) (1995) 481–499] proved that every graph with tree-width k ≥ 3 and maximum degree Δ ≥ 1 has tree-partition-width at most 24 k Δ . We prove that this bound is within a constant factor of optimal. In particular, for all k ≥ 3 and for all sufficiently large Δ , we construct a graph with tree-width k , maximum degree Δ , and tree-partition-width at least ( 1 8 − ϵ ) k Δ . Moreover, we slightly improve the upper bound to 5 2 ( k + 1 ) ( 7 2 Δ − 1 ) without the restriction that k ≥ 3 .