Isometric quasi-isometry in bounded tree-width
Open question on Theorem 1.2 with $L=1$ · arXiv:2501.09839
Status partial medium confidence
The open question of whether Theorem 1.2 of Nguyen–Scott–Seymour holds with $L=1$ (i.e., whether an additive quasi-isometry to a graph of bounded tree-width always suffices) remains unresolved in full generality. The sequel paper arXiv:2509.09031 establishes $L=1$ for path-width but not tree-width. A partial result (arXiv:2503.00798) achieves additive quasi-isometry ($L=1$) to graphs of tree-width at most two for the special class of $K_{2,3}$-induced minor-free graphs, indicating partial progress on the conjecture for restricted graph classes.
Cited literature (3)
-
Proves that L=1 (additive quasi-isometry) suffices for path-width, but does not resolve the analogous L=1 question for tree-width posed in Theorem 1.2.
-
partial $K_{2,3}$-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two (2025)
Establishes L=1 (additive quasi-isometry) to graphs of tree-width at most two for the special class of K_{2,3}-induced minor-free graphs, giving partial positive evidence for the conjecture on a restricted graph class.
-
partial An alternative characterisation of graphs quasi-isometric to graphs of bounded treewidth (2025)
Provides an alternative structural characterisation of graphs quasi-isometric to bounded treewidth graphs, complementary to Theorem 1.2, but does not address the L=1 question.
Reviewer notes. The L=1 question for tree-width is explicitly open in the source paper, contrasted with Theorem 1.3 where L=1 holds for path-width. arXiv:2503.00798 provides partial positive evidence for a special graph class (K_{2,3}-induced minor-free, tree-width ≤ 2) but its abstract does not explicitly cite arXiv:2501.09839; the connection is inferred from overlapping mathematical content. Confidence is medium because the full paper of 2503.00798 was not read to confirm it frames itself as progress on this specific open question.
Context
Theorem 1.2 extends the result of Berger and Seymour (Theorem 1.1) from trees to graphs of bounded tree-width, establishing that a graph admitting a tree-decomposition whose bags are each contained in the union of a bounded number of balls of bounded radius admits an $(L,C)$-quasi-isometry to a graph of bounded tree-width. The authors note that unlike the tree case (where $L=1$ is achievable), it is unknown whether $L=1$ suffices in the general bounded-tree-width setting.
Notes. Stated as a parenthetical remark in the introduction rather than a labelled conjecture/question environment. Only the first 4000 characters of the introduction were provided; additional open problems later in the paper may not be captured.
Source paper
Asymptotic structure. I. Coarse tree-width
Tung Nguyen, Alex Scott, Paul Seymour · 2025-09-05
https://arxiv.org/abs/2501.09839