1Fachbereich Mathematik, Universität Hamburg, Hamburg, Germany 2Institute of Geometry, TU Graz, Graz, Austria
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 507-510
Citer cet article
Nathan Bowler; Joshua Erde; Florian Lehner; Max Pitz; Nathan Bowler; Joshua Erde; Florian Lehner; Max Pitz. Bounding the cop number of a graph by its genus. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 507-510. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a23/
@article{AMUC_2019_88_3_a23,
author = {Nathan Bowler and Joshua Erde and Florian Lehner and Max Pitz and Nathan Bowler and Joshua Erde and Florian Lehner and Max Pitz},
title = { Bounding the cop number of a graph by its genus},
journal = {Acta mathematica Universitatis Comenianae},
pages = {507--510},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a23/}
}
TY - JOUR
AU - Nathan Bowler
AU - Joshua Erde
AU - Florian Lehner
AU - Max Pitz
AU - Nathan Bowler
AU - Joshua Erde
AU - Florian Lehner
AU - Max Pitz
TI - Bounding the cop number of a graph by its genus
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 507
EP - 510
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a23/
ID - AMUC_2019_88_3_a23
ER -
%0 Journal Article
%A Nathan Bowler
%A Joshua Erde
%A Florian Lehner
%A Max Pitz
%A Nathan Bowler
%A Joshua Erde
%A Florian Lehner
%A Max Pitz
%T Bounding the cop number of a graph by its genus
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 507-510
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a23/
%F AMUC_2019_88_3_a23
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$.
