Quasi-isometry distortion improvement for subdivision-closed classes

Conjecture 1.2 · arXiv:2509.09031

arXiv Conjecture high confidence— first stated 2025-10-02

Authors: Tung Nguyen, Alex Scott, Paul Seymour

Status open high confidence

Conjecture 1.2 from arXiv:2509.09031 proposes that for any graph class closed under edge contraction and edge subdivision, every (L,C)-quasi-isometry to a member of the class can be upgraded to a (1,C')-quasi-isometry. The source paper itself proves the special case where the class consists of graphs of bounded path-width. No post-October-2025 paper specifically resolving the full conjecture was found in a 5-call web search. A March 2025 paper (arXiv:2503.00798) on K_{2,3}-induced minor-free graphs establishes a related quasi-isometry result for bounded tree-width classes, but it predates this conjecture's statement.

Reviewer notes. The conjecture is ≤ 1 year old (October 2025). The paper proves the bounded path-width special case. arXiv:2503.07448 (March 2025) reportedly disproves a conjecture about multiplicative-to-additive distortion improvement for general graphs, but that is distinct from Conjecture 1.2 which restricts to classes closed under edge contraction and subdivision. arXiv:2503.00798 (Chakraborty, March 2025) on K_{2,3}-induced minor-free graphs predates 2509.09031 and so cannot be a follow-up. No verified post-statement resolution was found.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $\mathcal{C}$ be a class of connected graphs, closed under contracting edges and subdividing edges. For all $L,C$ there exists $C^{\prime}$ such that if there is an $(L,C)$-quasi-isometry from a graph $G$ to a member of $\mathcal{C}$, then there is a $(1,C^{\prime})$-quasi-isometry from $G$ to a member of $\mathcal{C}$.

Context

Motivated by a theorem of Chepoi, Dragan, Newman, Rabinovich, and Vaxès showing that $(L,C)$-quasi-isometry to a tree implies $(1,C')$-quasi-isometry to a tree, the authors ask for which graph classes $\mathcal{C}$ such a multiplicative-to-additive distortion improvement holds. Closure under edge subdivision and edge contraction is identified as a necessary condition, and the conjecture proposes it is also sufficient. The paper proves a special case: when $\mathcal{C}$ is the class of graphs of bounded path-width.

Source paper

Asymptotic structure. II. Path-width and additive quasi-isometry
Tung Nguyen, Alex Scott, Paul Seymour · 2025-10-02
https://arxiv.org/abs/2509.09031