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

profile\(k\)-blocktangletree-decompositionconnectivityTutte 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

• scientific article; zbMATH DE number 3882430 (Why is no real title available?)
• 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
• Vertex cuts
• \(k\)-blocks: a connectivity invariant for graphs

Cited in

(16)

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

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)