# zbMATH — the first resource for mathematics

Tree width and tangles: A new connectivity measure and some applications. (English) Zbl 0895.05034
Bailey, R. A. (ed.), Surveys in combinatorics, 1997. Proceedings of the 16th British combinatorial conference, London, UK, July 1997. London: Cambridge University Press. Lond. Math. Soc. Lect. Note Ser. 241, 87-162 (1997).
N. Robertson and P. D. Seymour [J. Algorithms 7, 309-322 (1986; Zbl 0611.05017), or J. Comb. Theory, Ser. B 48, No. 2, 227-254 (1990; Zbl 0719.05032)] developed the theory of tree decomposition of graphs and introduced the tree width, a connectivity invariant of graphs (mostly of infinite type) focussing on global properties of graphs.
The author discusses a new connectivity invariant, the bramble number, of a graph $$G$$. A bramble is a set of connected subgraphs of $$G$$, any two of which intersect or are joined by an edge. Then the order of a bramble $$\beta$$ is the minimum cardinality of a set of vertices which intersects every element of $$\beta$$. The bramble number $$\text{BN} (G)$$ of $$G$$ is the maximum of the orders of its brambles.
For any graph $$G$$, the tree width of $$G$$ is equal to $$\text{BN} (G)-1$$, see also P. D. Seymour and R. Thomas [J. Comb. Theory, Ser. B 58, No. 1, 22-23 (1993; Zbl 0795.05110)]. Besides the proof of this theorem, the author examines also the structure of graphs with large bramble numbers and resolves many questions on such graphs.
For the entire collection see [Zbl 0869.00029].
Reviewer: M.Hager (Leonberg)

##### MSC:
 05C40 Connectivity 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C10 Planar graphs; geometric and topological aspects of graph theory 05C38 Paths and cycles