Canonical trees of tree-decompositions

DOI10.1016/J.JCTB.2021.08.004MaRDI QIDQ2664548zbMATH OpenOpenAlexFDO

Authors Johannes Carmesin, Matthias Hamann, Babak Miraftab

Publication date 17 November 2021

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

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

zbMATH Keywords

automorphisms-group invariant tree-decompositionsgraph automorphismstangle

Mathematics Subject Classification ID

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

Abstract: We prove that every graph has a canonical tree of tree-decompositions that distinguishes all principal tangles (these include the ends and various kinds of large finite dense structures) efficiently. Here `trees of tree-decompositions' are a slightly weaker notion than `tree-decompositions' but much more well-behaved than `tree-like metric spaces'. This theorem is best possible in the sense that we give an example that `trees of tree-decompositions' cannot be strengthened to `tree-decompositions' in the above theorem. This implies results of Dunwoody and Kr"on as well as of Carmesin, Diestel, Hundertmark and Stein. Beyond that for locally finite graphs our result gives for each $kinmathbbN$ canonical tree-decompositions that distinguish all $k$-distinguishable ends efficiently.

Review text

Trees of tree-decompositions can be deemed as a class of tree decompositions. Here every part of each of these tree-decompositions is modified by another tree-decomposition. It can be naturally grouped for finite graphs, as single tree-decomposition. The authors opine that \textit{N. Robertson} and \textit{P. D. Seymour}'s tangle tree theorem [J. Comb. Theory, Ser. B 52, No. 2, 153--190 (1991; Zbl 0764.05069)] can be generalized to infinite graphs, in that one can get a canonical tree of tree-decompositions distinguishing the principal tangles. This result is best possible in the sense of their example that `trees of tree-decompositions' cannot be strengthened to `tree decompositions'. Moreover, the authors prove that for locally finite graphs it provides for every $k\in N$ natural tree-decompositions that separates out each $k$-distinguishable end tactfully. The ideas involved here in proofs are mind blowing and original.

Recommendations

• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Refining a tree-decomposition which distinguishes tangles
• End spaces and tree-decompositions
• All graphs have tree-decompositions displaying their topological ends

Cites work

• All graphs have tree-decompositions displaying their topological ends
• Canonical tree-decompositions of a graph that display its k-blocks
• Connectivity and tree structure in finite graphs
• Cutting up graphs revisited -- a short proof of Stallings' structure theorem.
• Graph minors. X: Obstructions to tree-decomposition
• Graph theory
• Lattices of cuts in graphs
• Profiles of separations: in graphs, matroids, and beyond
• Representations of infinite tree sets
• Vertex cuts

Cited in

(25)

• Canonical representatives for patterns of tree maps
• A tree-of-tangles theorem for infinite tangles
• Tangle-tree duality in abstract separation systems
• Profiles of separations: in graphs, matroids, and beyond
• Canonical tree-decompositions of finite graphs. II. Essential parts
• Countably determined ends and graphs
• A Stallings type theorem for quasi-transitive graphs
• scientific article; zbMATH DE number 4011953 (Why is no real title available?)
• Dulmage-Mendelsohn canonical decomposition as a generic pruning technique
• Trees of tangles in infinite separation systems
• Refining a tree-decomposition which distinguishes tangles
• End spaces and tree-decompositions
• Entanglements
• Efficiently distinguishing all tangles in locally finite graphs
• The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem
• Quasi-transitive \(K_{\infty}\)-minor free graphs
• Counterexamples regarding linked and lean tree-decompositions of infinite graphs
• A note on the structure of locally finite planar quasi-transitive graphs
• Refining tree-decompositions so that they display the k-blocks
• The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem (extended abstract)
• A full Halin grid theorem
• Coarse cops and robber in graphs and groups
• A representation theorem for end spaces of infinite graphs
• A short proof that every finite graph has a tree-decomposition displaying its tangles
• Canonical tree-decompositions of finite graphs. I: Existence and algorithms.

This page was built for publication: Canonical trees of tree-decompositions

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