# Bounding the cop number of a graph by its genus

## Main Article Content

## Abstract

The game of cops and robbers is a pursuit game played on a graph $G$ in which a group of cops tries to catch a robber, where both are allowed to move along to edges of $G$. The cop number of $G$, denoted by $c(G)$, is the smallest number of cops needed to catch a robber on $G$. Schr\"{o}der showed that $c(G) \leq \lfloor \frac{3}{2}\rfloor g(G) +3$, where $g(G)$ is the genus of $G$, that is, the smallest $k$ such that $G$ can be drawn on an orientable surface of genus $k$. Furthermore, he conjectured that this bound could be improved to $c(G) \leq g(G) +3$. By relating the game of cops and robbers to a topological game played on a surface we prove that $c(G) \leq \lceil \frac{4}{3} g(G) \rceil +3$.

## Article Details

How to Cite

Bowler, N., Erde, J., Lehner, F., & Pitz, M.
(2019).
Bounding the cop number of a graph by its genus.

*Acta Mathematica Universitatis Comenianae, 88*(3), 507-510. Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1209/688
Issue

Section

EUROCOMB 2019