On tree-partition-width

A tree-partition   of a graph GG 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 GG is the minimum width of a tree-partition of GG. 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≥3k≥3 and maximum degree Δ≥1Δ≥1 has tree-partition-width at most 24kΔ24kΔ. We prove that this bound is within a constant factor of optimal. In particular, for all k≥3k≥3 and for all sufficiently large ΔΔ, we construct a graph with tree-width kk, maximum degree ΔΔ, and tree-partition-width at least (18−ϵ)kΔ. Moreover, we slightly improve the upper bound to 52(k+1)(72Δ−1) without the restriction that k≥3k≥3.