Skip to main navigation Skip to search Skip to main content

Refining a tree-decomposition which distinguishes tangles

Research output: Contribution to journal › Article › peer-review

Abstract

Roberston and Seymour introduced tangles of order κ as objects representing highly connected parts of a graph and showed that every graph admits a tree-decomposition of adhesion κ in which each tangle of order κ is contained in a dierent part. Recently, Carmesin, Diestel, Hamann, and Hundertmark showed that such a tree-decomposition can be constructed in a canonical way, which makes it invariant under automorphisms of the graph. These canonical tree-decompositions necessarily have parts which contain no tangle of order κ, which we call inessential. Diestel asked what could be said about the structure of the inessential parts. In this paper we show that the torsos of the inessential parts in these tree-decompositions have branch-width κ, allowing us to further refine the canonical tree-decompositions and also show that a similar result holds for κ-blocks. We also use our methods to further rene the essential parts in such a tree-decomposition in a similar fashion.

Original languageEnglish
Pages (from-to)1529-1551
Number of pages23
JournalSIAM Journal on Discrete Mathematics
Volume31
Issue number3
DOIs
Publication statusPublished - 2017

Bibliographical note

Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics.

Keywords

  • Graph
  • Profile
  • Tangle
  • Tree-decomposition
  • κ-block

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Refining a tree-decomposition which distinguishes tangles'. Together they form a unique fingerprint.

Cite this