A simple proof of the tree-width duality theorem

We give a simple proof of 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.

Data and Resources

Additional Info

Field Value
Source https://hal.science/hal-00859912
Author Mazoit, Frédéric
Maintainer CCSD
Last Updated May 9, 2026, 19:46 (UTC)
Created May 9, 2026, 19:46 (UTC)
Identifier hal-00859912
Language en
Rights https://about.hal.science/hal-authorisation-v1/
contributor Laboratoire Bordelais de Recherche en Informatique (LaBRI) ; Université de Bordeaux (UB)-École Nationale Supérieure d'Électronique, Informatique et Radiocommunications de Bordeaux (ENSEIRB)-Centre National de la Recherche Scientifique (CNRS)
creator Mazoit, Frédéric
date 2013-09-09T00:00:00
harvest_object_id 9a9a5533-842f-4139-bca9-29d41b074581
harvest_source_id 3374d638-d20b-4672-ba96-a23232d55657
harvest_source_title test moissonnage SELUNE
metadata_modified 2025-05-26T00:00:00
relation info:eu-repo/semantics/altIdentifier/arxiv/1309.2266
set_spec type:REPORT