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) 48 1-499] proved that every graph with tree-widdi k >= 3 and maximum degree Delta >= 1 has tree-partition-width at most 24k Delta. We prove that this bound is within a constant factor of optimal. In particular, for all k >= 3 and for all Sufficiently large A, we construct a graph with tree-width k, maximum degree Delta, and tree-partition-width at least ((1)/(8) - is an element of)k Delta. Moreover, we slightly improve the upper bound to (5)/(2) (k + 1) ((7)/(2)Delta - 1) without the restriction that k >= 3. (C) 2009 Elsevier Ltd. All rights reserved.