Sublinear cop number vs treedepth
Problem 9 · arXiv:2602.07435
Status open high confidence
Problem 9 asks whether cop(G) = o(td(G)) for connected graphs G. The authors of arXiv:2602.07435 establish that cop(G) ≤ ½(td(G)+1) follows easily from existing bounds on cop number in terms of treewidth, and note that improving significantly on this linear bound appears difficult. No follow-up paper addressing this specific open problem was found in the three months since the paper was posted.
Reviewer notes. The conjecture is only about 3 months old as of the review date. The paper HTML confirms that cop(G) ≤ ½(td(G)+1) is the current best bound (derived from treewidth results), and that the authors view a sublinear improvement as an open challenge. Louis Esperet's publications page lists one related 2026 paper ('Coarse cops and robber in graphs and groups', arXiv:2502.15571) but that concerns a coarse-geometry variant unrelated to Problem 9. No evidence of any resolution was found.
Context
The authors ask whether a sublinear bound on the cop number in terms of treedepth holds, viewing treedepth as a natural intermediate parameter between vertex cover number and treewidth. They note that the bound $\operatorname{cop}(G)\leqslant\tfrac{1}{2}(\mathrm{td}(G)+1)$ is easily deducible from existing results on treewidth, but improving significantly on it seems difficult.
Source paper
Cops and robber in graphs with bounded vertex cover number
Prosenjit Bose, Louis Esperet, Jędrzej Hodor, Gwenaël Joret, Piotr Micek, Clément Rambaud · 2026-02-07
https://arxiv.org/abs/2602.07435