Graph-theory open problems

Scol bounded by bramble number in polynomial expansion

Question 2 · arXiv:2502.04177

arXiv Question high confidence— first stated 2025-09-15
Authors: Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, Piotr Micek

Status open high confidence

Question 2 of arXiv:2502.04177 asks whether, for every graph class with polynomial expansion, the strong r-coloring number scol_r(G) is polynomially bounded by the depth-r bramble number bn_r(G). The paper itself establishes that the depth-r bramble number and several related parameters (depth-r tangle number, linkedness, well-linkedness) are pairwise polynomially related in polynomial-expansion classes, but the connection to scol_r(G) is left open. No follow-up paper resolving this question was found in the indexed literature as of May 2026.

Reviewer notes. No follow-up paper addressing Question 2 was found after three targeted web searches and two direct fetches of the source paper. The paper was published in DMTCS (September 2025) shortly after the arXiv preprint (February 2025). The conjecture is recent (less than 1 year at time of review), and absence of follow-up is expected. The polynomial expansion assumption is noted in the paper as essential: without it scol_r cannot be bounded by any function of r and bn_{g(r)}(G).

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

Question. Is it true that for every graph class $\mathcal{C}$ with polynomial expansion, there exists a polynomial function $f$ such that for every integer $r\geqslant 0$ and every graph $G\in\mathcal{C}$, $$\mathrm{scol}_{r}(G)\leqslant f(r,\mathrm{bn}_{r}(G))?$$

Context

A positive answer to this question would be sufficient to answer Question 1 positively. The polynomial expansion assumption on $\mathcal{C}$ is essential: without it, $\mathrm{scol}_r(G)$ cannot be bounded by any function of $r$ and the depth-$r$ bramble number $\mathrm{bn}_r(G)$, even if the bramble number is replaced by $\mathrm{bn}_{g(r)}(G)$ for an arbitrary function $g$.

Also stated in

Source paper

Shallow brambles
Nicolas Bousquet, Wouter Cames van Batenburg, Louis Esperet, Gwenaël Joret, Piotr Micek · 2025-09-15
https://arxiv.org/abs/2502.04177