Some results on tree decomposition of graphs
Guoli Ding, Bogdan Oporowski · Journal of Graph Theory · 1995
Abstract We investigate tree decompositions ( T ,( X t ) tϵV(T) ) whose width is “close to optimal” and such that all the subtrees of T induced by the vertices of the graph are “small.” We prove the existence of such decompositions for various interpretations of “close to optimal” and “small.” As a corollary of these results, we prove that the dilation of a graph is bounded by a logarithmic function of the congestion of the graph thereby settling a generalization of a conjecture of Bienstock. © 1995 John Wiley & Sons, Inc.