Canonical tree-decompositions of a graph that display its k-blocks

详细信息    查看全文

• 作者：Johannes Carmesin ; J. Pascal Gollin ^{pascal.gollin@uni-hamburg.de}
• 关键词：Graph ; Connectivity ; Tree-decomposition ; k-Block ; Tangle ; Profile
• 刊名：Journal of Combinatorial Theory, Series B
• 出版年：2017
• 出版时间：January 2017
• 年：2017
• 卷：122
• 期：Complete
• 页码：1-20
• 全文大小：460 K
• 卷排序：122

文摘

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.