Abstract:In this paper, we develop a coarse analogue of tree-width. We prove that a graph $G$ admits a tree-decomposition in which each bag is contained in the union of a bounded number of balls of bounded radius, if and only if $G$ admits a quasi-isometry to a graph with bounded tree-width. (The ``if'' half is easy, but the ``only if'' half is challenging.) This generalizes a recent result of Berger and Seymour, concerning tree-decompositions when each bag has bounded radius. We also prove a similar result for line-width, which is an extension of path-width to infinite graphs.
From: Tung H. Nguyen [view email]
[v1]
Thu, 16 Jan 2025 20:57:17 UTC (21 KB)
[v2]
Thu, 23 Jan 2025 18:38:37 UTC (23 KB)
[v3]
Fri, 5 Sep 2025 14:21:44 UTC (13 KB)
[v4]
Fri, 31 Jul 2026 22:59:13 UTC (23 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。