Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-08T09:28:25.999Z Has data issue: false hasContentIssue false
  • English
  • Français

Two Short Proofs Concerning Tree-Decompositions

Published online by Cambridge University Press:  21 November 2002

PATRICK BELLENBAUM  and
REINHARD DIESTEL
PATRICK BELLENBAUM
Affiliation:
Mathematisches Seminar der Universität Hamburg, Bundesstr. 55, D-20146 Hamburg, Germany (e-mail: diestel@math.uni-hamburg.de)
REINHARD DIESTEL
Affiliation:
Mathematisches Seminar der Universität Hamburg, Bundesstr. 55, D-20146 Hamburg, Germany (e-mail: diestel@math.uni-hamburg.de)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We give short proofs of the following two results: Thomas's theorem that every finite graph has a linked tree-decomposition of width no greater than its tree-width; and the ‘tree-width duality theorem’ of Seymour and Thomas, that the tree-width of a finite graph is exactly one less than the largest order of its brambles.

Information

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 11 , Issue 6 , November 2002 , pp. 541 - 547
Copyright
2002 Cambridge University Press