Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

DOI10.1016/J.JCTB.2014.04.001MaRDI QIDQ895993zbMATH OpenOpenAlexFDO

Authors Reinhard Diestel, Johannes Carmesin, Matthias Hamann, F. Hundertmark

Publication date 11 December 2015

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1305.4668

zbMATH Keywords

\(k\)-blockconnectivityprofiletangletree-decompositionTutte decomposition

Mathematics Subject Classification ID

Trees (05C05) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We construct tree-decompositions of graphs that distinguish all their k-blocks and tangles of order k, for any fixed integer k. We describe a family of algorithms to construct such decompositions, seeking to maximize their diversity subject to the requirement that they commute with graph isomorphisms. In particular, all the decompositions constructed are invariant under the automorphisms of the graph.

Recommendations

• Canonical tree-decompositions of finite graphs. II. Essential parts
• Canonical trees of tree-decompositions
• Refining a tree-decomposition which distinguishes tangles
• Computing with tangles
• Canonical tree-decompositions of a graph that display its k-blocks

Cites work

• \(k\)-blocks: a connectivity invariant for graphs
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Connectivity and tree structure in finite graphs
• Graph minors. X: Obstructions to tree-decomposition
• Graph theory
• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• Vertex cuts

Cited in

(20)

• Structural submodularity and tangles in abstract separation systems
• Abstract separation systems
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Canonical trees of tree-decompositions
• Splitting groups with cubic Cayley graphs of connectivity two
• Canonical tree-decompositions of a graph that display its k-blocks
• Connectivity and tree structure in finite graphs
• scientific article; zbMATH DE number 2016066 (Why is no real title available?)
• On the block number of graphs
• A canonical tree-of-tangles theorem for structurally submodular separation systems
• A short derivation of the structure theorem for graphs with excluded topological minors
• Refining a tree-decomposition which distinguishes tangles
• Entanglements
• Efficiently distinguishing all tangles in locally finite graphs
• Refining trees of tangles in abstract separation systems: inessential parts
• Characterising 4-tangles through a connectivity property
• Refining tree-decompositions so that they display the k-blocks
• Untangling Gaussian mixtures
• Optimal trees of tangles: refining the essential parts
• A short proof that every finite graph has a tree-decomposition displaying its tangles

This page was built for publication: Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q895993)