Bounding the cop number of a graph by its genus

Abstract

It is known that the cop number $c(G)$ of a connected graph $G$ can be bounded as a function of the genus of the graph $g(G)$. The best known bound, that $c(G)\le \lfloor \frac{3g(G)}{2}\rfloor +3$, was given by Schröder, who conjectured that in fact $c(G)\le g(G)+3$. We give the first improvement to Schröder's bound, showing that $c(G)\le \frac{4g(G)}{3}+\frac{10}{3}$.

36 pages