pith. sign in

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

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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.

fields

math.CO 1

years

2023 1

verdicts

UNVERDICTED 1

representative citing papers

Optimal trees of tangles: refining the essential parts

math.CO · 2023-04-24 · 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.

citing papers explorer

Showing 1 of 1 citing paper.

  • Optimal trees of tangles: refining the essential parts math.CO · 2023-04-24 · unverdicted · none · ref 5 · internal anchor

    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.