Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903867 | Journal of Combinatorial Theory, Series B | 2018 | 30 Pages |
Abstract
There are many results asserting the existence of tree-decompositions of minimal width which still represent local connectivity properties of the underlying graph, perhaps the best known being Thomas' theorem that proves for every graph G the existence of a linked tree-decomposition of width tw(G). We prove a general theorem on the existence of linked and lean tree-decompositions, providing a unifying proof of many known results in the field, as well as implying some new results. In particular we prove that every matroid M admits a lean tree-decomposition of width tw(M), generalizing the result of Thomas.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Joshua Erde,