On the tree-width of a graph

Research output: Contribution to journalArticlepeer-review


Robertson and Seymour introduced the concept of the 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 [Robertson, Seymour: Graph Minors. II. Algorithmic aspects of tree-width. J. Algorithms 7, 1986] . In the present paper several equivalent definitions of tree-width are discussed and tree-width of several families of graphs is determined.
Original languageEnglish
Pages (from-to)225-236
JournalActa Mathematica Universitatei Comenianae
Issue number2
Publication statusPublished - 1992


Dive into the research topics of 'On the tree-width of a graph'. Together they form a unique fingerprint.

Cite this