Canonical tree-decompositions of finite graphs II. Essential parts

Johannes Carmesin, Reinhard Diestel, Matthias Hamann, Fabian Hundertmark

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)
139 Downloads (Pure)

Abstract

In Part I of this series we described three algorithms that construct canonical tree-decompositions of graphs which distinguish all their k-blocks and tangles of order k. We now establish bounds on the number of parts in these decompositions that contain no such block or tangle, and determine conditions under which such parts contain nothing but a k-block.
Original languageEnglish
Pages (from-to)268-283
JournalJournal of Combinatorial Theory. Series B
Volume118
Early online date28 Aug 2015
DOIs
Publication statusPublished - May 2016

Bibliographical note

15 pages, 3 figures

Keywords

  • math.CO
  • graph
  • minor
  • tangle k-block
  • tree-decomposition

Fingerprint

Dive into the research topics of 'Canonical tree-decompositions of finite graphs II. Essential parts'. Together they form a unique fingerprint.

Cite this