Nguyen–Scott–Seymour conjecture on additive quasi-isometries to bounded-tree-width graphs
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 such that if a graph admits a quasi-isometry to a graph of tree-width at most two, then admits a quasi-isometry with additive distortion to a graph of tree-width at most .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.