SOME RESULTS ON TREE DECOMPOSITION OF GRAPHS

We investigate tree decompositions (T,(X(t))(t is an element of 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 ex istence 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 t he congestion of the graph thereby settling a generalization of a conj ecture of Bienstock. (C) 1995 John Wiley & Sons, Inc.