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

DOI10.1016/J.JCTB.2014.04.001zbMATH Open1327.05269arXiv1305.4668OpenAlexW1538190426MaRDI QIDQ895993FDOQ895993

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

Publication date: 11 December 2015

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Graph minors. X: Obstructions to tree-decomposition
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Connectivity and tree structure in finite graphs
• $k$-Blocks: A Connectivity Invariant for Graphs
• Vertex Cuts

Cited In (14)

• Canonical tree-decompositions of finite graphs. II. Essential parts
• Connectivity and tree structure in finite graphs
• Structural submodularity and tangles in abstract separation systems
• Entanglements
• Abstract separation systems
• A Short Derivation of the Structure Theorem for Graphs with Excluded Topological Minors
• On the Block Number of Graphs
• A short proof that every finite graph has a tree-decomposition displaying its tangles
• Refining trees of tangles in abstract separation systems: inessential parts
• Refining a Tree-Decomposition which Distinguishes Tangles
• Canonical tree-decompositions of a graph that display its \(k\)-blocks
• A canonical tree-of-tangles theorem for structurally submodular separation systems
• Title not available (Why is that?)
• Splitting groups with cubic Cayley graphs of connectivity two

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)