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 solved high confidence

The source paper itself proves polynomial bounds for the homothet and ball-like cases and gives an exponential counterexample for comparable boxes in dimension three.

Cited literature (1)

proof Weak Coloring Numbers of Intersection Graphs (2021)

See linked article · Existing literature or final source version

The source paper itself proves polynomial bounds for the homothet and ball-like cases and gives an exponential counterexample for comparable boxes in dimension three.

Read the literature-status audit

Reviewer notes. These status corrections report results attributed to existing papers or to the final source version. Graph-Theory-LLM-Proofs located and checked the implication; it is not credited as the author of the result. Audit caveat: The conclusion fixes the geometric parameters as in the source; any restriction excluding the three-dimensional comparable-box construction is a different question.

Auto-reviewed 2026-09-01 with gpt-5.6-sol.

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