Cop number √g growth rate by genus

Conjecture 8 · arXiv:1710.11281

arXiv Conjecture low confidence— first stated 2017-10-31

Author: Bojan Mohar

Status open high confidence

Mohar's Conjecture 8 posits that both the orientable cop number c(g) and the nonorientable cop number ec(g) grow as g^{1/2+o(1)} with genus g. The lower bound g^{1/2-o(1)} is already established via random graphs. The best known upper bound remains linear in g: Bowler, Erde, Lehner, and Pitz (arXiv:1911.01758, SIAM J. Discrete Math.) improved Schröder's bound to c(G) ≤ 4g(G)/3 + 10/3, but this is far above the conjectured g^{1/2+ε} threshold, leaving the conjecture fully open.

Cited literature (1)

partial Bounding the Cop Number of a Graph by Its Genus (2021)

Nathan Bowler, Joshua Erde, Florian Lehner, Max Pitz · SIAM Journal on Discrete Mathematics · arXiv:1911.01758 · doi:10.1137/20M1312150

Improves the upper bound on cop number by genus to c(G) ≤ 4g(G)/3 + 10/3, better than Schröder's classical bound, but still linear in g and far from the conjectured g^{1/2+o(1)}.

Reviewer notes. The conjecture is open with a large gap: the lower bound is g^{1/2-o(1)} (random graphs) while the best upper bound is O(g), not O(g^{1/2+ε}). No paper has resolved the conjecture for either c(g) or ec(g). The Springer chapter 'Improved Bounds on the Cop Number of a Graph Drawn on a Surface' (2021, doi:10.1007/978-3-030-83823-2_18) could not be verified due to paywall.

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

Conjecture. $c(g) = g^{\frac{1}{2}+o(1)}$ and $ec(g) = g^{\frac{1}{2}+o(1)}$. In other words, for every $\varepsilon > 0$ there exists $g_0$ such that for every $g \geq g_0$, $$g^{\frac{1}{2}-\varepsilon} < c(g) < g^{\frac{1}{2}+\varepsilon}$$ and $$g^{\frac{1}{2}-\varepsilon} < ec(g) < g^{\frac{1}{2}+\varepsilon}.$$

Context

After establishing via random graphs that $c(g) \geq g^{1/2-o(1)}$, the author conjectures the true growth rate of the cop number (and nonorientable cop number) as a function of genus is exactly $g^{1/2}$. The conjecture has been unchallenged as of the writing of the notes.

Notes. PDF source — exponents appear garbled in extraction (e.g., 'g 1 2 +o(1)'); reconstructed as $g^{1/2+o(1)}$ from context. The conjecture is explicitly labelled 'Conjecture 8 (Mohar, 2009)' and is the paper author's own.

Source paper

Notes on Cops and Robber game on graphs
Bojan Mohar · 2017-10-31
https://arxiv.org/abs/1710.11281 PDF source