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

Yes: the finite-state bound gives capt_k(G) <= n^{c(G)+1} for every k >= c(G), and hence Schroeder's conjecture immediately yields capt_k(G) <= n^{g+4}.

Cited literature (1)

proof Topological directions in Cops and Robbers (2017)

See linked article · Existing literature or final source version

Yes: the finite-state bound gives capt_k(G) <= n^{c(G)+1} for every k >= c(G), and hence Schroeder's conjecture immediately yields capt_k(G) <= n^{g+4}.

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: This does not prove Schroeder's conjecture or any sharper surface-specific capture-time bound.

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

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