pith. sign in

arxiv: 1506.02904 · v1 · pith:R44VFROVnew · submitted 2015-06-09 · 🧮 math.CO

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

classification 🧮 math.CO
keywords blockgraphlessadhesionblockscanonicaldiestelevery
0
0 comments X
read the original 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, Diestel, Hamann, Hundertmark and Stein 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Optimal trees of tangles: refining the essential parts

    math.CO 2023-04 unverdicted novelty 7.0

    A single theorem showing that any efficient k-tangle-distinguishing tree-decomposition of a graph can be refined so each part is either too small for a k-tangle or minimal while containing one.