Abstract
A k-block in a graph G is a maximal set of at least k vertices no two of which can be separated in G by removing less than k vertices. It is separable if there exists a tree-decomposition of adhesion less than k of G in which this k-block appears as a part.
Carmesin et al. proved that every finite graph has a canonical tree-decomposition of adhesion less than k that distinguishes all its k-blocks and tangles of order k. We construct such tree-decompositions with the additional property that every separable k-block is equal to the unique part in which it is contained. This proves a conjecture of Diestel.
Carmesin et al. proved that every finite graph has a canonical tree-decomposition of adhesion less than k that distinguishes all its k-blocks and tangles of order k. We construct such tree-decompositions with the additional property that every separable k-block is equal to the unique part in which it is contained. This proves a conjecture of Diestel.
Original language | English |
---|---|
Pages (from-to) | 1-20 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 122 |
Early online date | 28 Jun 2016 |
DOIs | |
Publication status | Published - 1 Jan 2017 |
Keywords
- math.CO
- graph
- connectivity
- tree-decomposition
- k-block
- tangle
- profile