Polynomial weak coloring numbers for thin intersection graphs

Question (polynomial weak coloring numbers for intersection graph classes) · arXiv:2103.17094

arXiv Question medium confidence— first stated 2021-04-07

Authors: Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, Yelena Yuditsky

Status open high confidence

The question asks whether the k-th weak coloring numbers are polynomial in k for the restricted intersection graph classes of Lemma 1 (t-thin sets of convex objects, comparable axis-aligned boxes, b-ball-like objects), motivated by the possible survival of the Joret–Wood conjecture in the geometric setting after Grohe et al.'s edge-subdivision disproof in the general setting. No follow-up paper resolving this question was found in the indexed literature as of May 2026. The 2024 paper on weak coloring numbers of minor-closed graph classes (arXiv:2407.04588, SODA 2025) addresses polynomial bounds for a different class of graphs (X-minor-free graphs) and does not touch the geometric intersection graph question.

Reviewer notes. The source paper itself (published at SoCG 2022) demonstrates that for comparable axis-aligned boxes the weak coloring numbers are exponential, which gives a negative answer for part of class (a). The open question appears to concern whether the exponential dependence might be avoidable for the more tightly constrained sub-classes of Lemma 1 (e.g., homothets of a fixed centrally symmetric convex body or b-ball-like objects). No paper specifically resolving this was found after 5 web calls.

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

Question. Are the $k$-th weak coloring numbers polynomial in $k$ for the graph classes described in Lemma 1: intersection graphs of $t$-thin sets of (a) scaled and translated copies of the same centrally symmetric compact convex object, or comparable axis-aligned boxes; or (b) $b$-ball-like objects for some $b\geq 1$?

Context

Joret and Wood conjectured that every graph class with polynomial strong coloring numbers also has polynomial weak coloring numbers; Grohe et al. disproved this via edge-subdivision constructions. The authors argue the conjecture might still hold for natural geometric classes such as those covered by Lemma 1 (thin intersection graphs of convex objects in $\mathbb{R}^d$), and explicitly ask whether this is the case.

Notes. Stated as a prose question without a labelled theorem environment. Theorem 3 of the paper gives polynomial (in $k$) upper bounds for scaled/translated centrally symmetric objects and $b$-ball-like objects, giving a positive partial answer; Theorem 4(i) shows exponential lower bounds for touching comparable axis-aligned boxes in $\mathbb{R}^3$, giving a negative answer for that subclass. PDF source — surrounding math may be garbled in the extracted text.

Source paper

Weak Coloring Numbers of Intersection Graphs
Zdeněk Dvořák, Jakub Pekárek, Torsten Ueckerdt, Yelena Yuditsky · 2021-04-07
https://arxiv.org/abs/2103.17094 PDF source