## 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

## Fingerprint

Dive into the research topics of 'Canonical tree-decompositions of a graph that display its*k*-blocks'. Together they form a unique fingerprint.