|国家预印本平台
首页|Counterexamples regarding linked and lean tree-decompositions of infinite graphs

Counterexamples regarding linked and lean tree-decompositions of infinite graphs

Counterexamples regarding linked and lean tree-decompositions of infinite graphs

来源:Arxiv_logoArxiv
英文摘要

Kriz and Thomas showed that every (finite or infinite) graph of tree-width $k \in \mathbb{N}$ 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.

Sandra Albrechtsen、Max Pitz、Raphael W. Jacobs、Paul Knappe

数学

Sandra Albrechtsen,Max Pitz,Raphael W. Jacobs,Paul Knappe.Counterexamples regarding linked and lean tree-decompositions of infinite graphs[EB/OL].(2025-07-16)[2025-08-10].https://arxiv.org/abs/2405.06755.点此复制

评论