Entanglements

DOI10.1016/J.JCTB.2023.08.007MaRDI QIDQ6144391zbMATH OpenOpenAlexFDO

Authors Johannes Carmesin, Jan Kurkofka

Publication date 29 January 2024

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

canonicalefficiently distinguishentanglementnested set of separationstree of tangles

Mathematics Subject Classification ID

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

Abstract: Robertson and Seymour constructed for every graph $G$ a tree-decomposition that efficiently distinguishes all the tangles in $G$. While all previous constructions of these decompositions are iterative in nature, we give an explicit one-step construction. The key ingredient is an axiomatisation of 'local properties' of tangles. Generalisations to locally finite graphs and matroids are also discussed.

Recommendations

• A short proof that every finite graph has a tree-decomposition displaying its tangles
• Canonical trees of tree-decompositions
• Refining a tree-decomposition which distinguishes tangles
• Efficiently distinguishing all tangles in locally finite graphs
• Computing with tangles

Cites work

• A short proof that every finite graph has a tree-decomposition displaying its tangles
• A tree-of-tangles theorem for infinite tangles
• Abstract separation systems
• All graphs have tree-decompositions displaying their topological ends
• Canonical tree-decompositions of a graph that display its k-blocks
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Canonical trees of tree-decompositions
• Graph minors. X: Obstructions to tree-decomposition
• Graph theory
• Local 2-separators
• Profiles of separations: in graphs, matroids, and beyond
• Tree sets
• Trees of tangles in abstract separation systems

Cited in

(4)

• 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

This page was built for publication: Entanglements

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