Counterexamples regarding linked and lean tree-decompositions of infinite graphs

2024/05/10 by Albrechtsen, Sandra, Jacobs, Raphael W., Knappe, Paul +1 · 2 citations
#05C05 #05C40 #05C63 #05C83 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2405.06755

Abstract

Kriz and Thomas showed that every (finite or infinite) graph of tree-width k ∈ ℕ admits a lean tree-decomposition of width k. We discuss a number of counterexamples demonstrating the limits of possible generalisations of their result to arbitrary infinite tree-width. In particular, we construct a locally finite, planar, connected graph that has no lean tree-decomposition.

Cited by

• Canonical tree-decompositions of chordal graphs
• Displaying prescribed sets of ends by linked tree-decompositions

Related

• A unified treatment of linked and lean tree-decompositions
• A Menger-like property of tree-cut width
• Non-branching tree-decompositions
• Linked tree-decompositions into finite parts
• Asymptotic structure. III. Excluding a fat tree