Nguyen–Scott–Seymour conjecture on additive quasi-isometries to bounded-tree-width graphs

A graph is quasi-isometric to another graph if there is a quasi-isometry between their metric spaces; a quasi-isometry with additive distortion has bounded additive error in distances. The tree-width of a graph is the minimum width of a tree-decomposition of the graph.

Nguyen–Scott–Seymour conjecture. There is a constant kk such that if a graph GG admits a quasi-isometry to a graph of tree-width at most two, then GG admits a quasi-isometry with additive distortion to a graph of tree-width at most kk.

This conjecture asks whether quasi-isometry to graphs of tree-width two can always be improved to a quasi-isometry with only additive distortion while retaining bounded tree-width. The supplied context presents it as a conjecture and does not state a resolution.

Sources & referencesView supporting material

Primary source

Dibyayan Chakraborty, “K_2,3-induced minor-free graphs admit quasi-isometry with additive distortion to graphs of tree-width at most two”, arXiv:2503.00798 (2026).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.