Capture time bounds for genus-g graphs

Capture time bounds for higher genus graphs · arXiv:1709.09050

arXiv Question medium confidence— first stated 2018-04-22

Authors: Anthony Bonato, Bojan Mohar

Status open high confidence

The question asks whether capt_k(G) = O(n^{g+4}) holds for genus-g graphs whenever k >= g+3, conditional on Schroeder's conjecture (c(G) <= g+3 for genus g). Schroeder's conjecture itself remains open beyond the planar and toroidal cases, making the capture-time question doubly open. Kinnersley (2019) established that the general bound O(n^{k+1}) is tight for arbitrary graphs, but no work specifically addresses the genus-restricted capture-time question. No resolution has been found in the literature.

Reviewer notes. Schroeder's conjecture (c(G) <= g+3 for genus-g graphs) remains open for g >= 2, so the conditional question about capt_k(G) = O(n^{g+4}) has not been addressed. The general tight bound O(n^{k+1}) for capture time (Kinnersley) does not specialise to a genus-dependent improvement. The 2025 paper arXiv:2504.13813 on cops and robbers for graphs on surfaces with crossings uses a different distance-d variant and does not address this question. No follow-up found in indexed literature.

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

Question. What are the bounds on the capture time for graphs of higher genus? If Schroeder's conjecture holds and $\gamma(G) = g$, is it true that $\mathrm{capt}_k(G) = O(n^{g+4})$ for every $k \geq g+3$?

Context

The paper identifies bounding the capture time of graphs embedded on surfaces as an interesting open question. If Schroeder's conjecture holds, giving $c(G) \leq g+3$ for genus-$g$ graphs, then a natural bound on $\mathrm{capt}_k(G)$ would follow for $k \geq g+3$.

Notes. PDF source

Source paper

Topological directions in Cops and Robbers
Anthony Bonato, Bojan Mohar · 2018-04-22
https://arxiv.org/abs/1709.09050 PDF source