Tame representation for polynomial strong coloring numbers

Question 6 · arXiv:2001.01552

arXiv Question high confidence— first stated 2020-01-06

Authors: Zdenek Dvorak, Rose McCarty, Sergey Norin

Status open medium confidence

Question 6 asks whether polynomial strong coloring numbers (col_r(G) ≤ p(r) for all r) force a graph to admit a (c, ⊑_s)-tame geometric representation in some R^d, which would give a geometric characterization of graphs with polynomially bounded strong coloring numbers analogous to Krauthgamer–Lee's grid-embedding characterization of polynomial-growth classes. No follow-up paper resolving this question in either direction was found in a systematic search of the literature through May 2026. Related work on weak coloring numbers of intersection graphs (Dvořák, Pekárek, Ueckerdt, Yuditsky, SoCG 2022) and on strongly sublinear separators for sphere intersection graphs (Davies et al., SoCG 2025) works in adjacent territory but does not address this specific question.

Reviewer notes. No follow-up resolving Question 6 was found despite 5 web calls covering the period 2020–2026. The question is now 5+ years old, making the medium confidence appropriate — a wide search returned no resolution but the conjecture is old enough that absence of evidence is worth noting. The paper was published in SIAM J. Discrete Math. 35(2):1149–1164, 2021. Dvořák, Pekárek, Ueckerdt, and Yuditsky (SoCG 2022, arXiv:2106.02537 region) studied weak/strong coloring numbers of intersection graphs but did not address the tame-representation direction of Question 6. Davies, Georgakopoulos, Hatzel, McCarty (SoCG 2025) proved strongly sublinear separators and bounded asymptotic dimension for sphere intersection graphs excluding K_{t,t}, again adjacent but not resolving Question 6.

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

Question. Given a polynomial $p$, do there necessarily exist real numbers $c, s \geq 1$ and a positive integer $d$, such that the following holds: every graph $G$ satisfying $\mathrm{col}_r(G) \leq p(r)$ for every non-negative integer $r$ admits a $(c, \sqsubseteq_s)$-tame representation in $\mathbb{R}^d$?

Context

Theorem 4 shows that graphs with $(c,\sqsubseteq_s)$-tame representations in $\mathbb{R}^d$ have strong coloring numbers bounded by $\delta r^d$, paralleling Krauthgamer–Lee's characterization (Theorem 5) of polynomial-growth graph classes via grid embeddings. Answering Question 6 would determine whether Theorem 4 yields an analogous geometric characterization of graphs with polynomially bounded strong coloring numbers.

Notes. The notation $(c,\sqsubseteq_s)$-tame and $\sqsubseteq_s$ are rendered as '(cid:118)s' in the PDF extraction; interpreted as the paper's comparability relation defined via volume overlap.

Source paper

Sublinear separators in intersection graphs of convex shapes
Zdenek Dvorak, Rose McCarty, Sergey Norin · 2020-01-06
https://arxiv.org/abs/2001.01552 PDF source