zbMATH — the first resource for mathematics

On the tree-width of a graph. (English) Zbl 0821.05014
Summary: Robertson and Seymour introduced the concept of tree-width of a graph. It plays an important role in their results on graph minors culminating in their proof of Wagner’s conjecture. This concept seems to be interesting from the algorithmic point of view as well: many graph problems that are NP-complete in general can be polynomially solvable if graphs are constrained to have bounded tree-width [N. Robertson and P. D. Seymour, J. Algorithms 7, 309-322 (1986; Zbl 0611.05017)]. In the present paper several equivalent definitions of tree-width are discussed and tree-width of several families of graphs is determined.

05C05 Trees
05C75 Structural characterization of families of graphs
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
Full Text: EMIS EuDML