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

Johannes Carmesin, Pascal Gollin

Research output: Contribution to journalArticlepeer-review

4 Citations (Scopus)
177 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)1-20
JournalJournal of Combinatorial Theory. Series B
Volume122
Early online date28 Jun 2016
DOIs
Publication statusPublished - 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.

Cite this