pith. sign in

arxiv: 1703.03756 · v1 · pith:3VQQ4RTQnew · submitted 2017-03-10 · 🧮 math.CO

A unified treatment of linked and lean tree-decompositions

classification 🧮 math.CO
keywords existenceleanlinkedresultstree-decompositionswidtheverygraph
0
0 comments X
read the original 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-decompositon 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.