Topological directions in Cops and Robbers

We survey results at the intersection of topological graph theory and the game of Cops and Robbers, focusing on results, conjectures, and open problems for the cop number of a graph embedded on a surface. After a discussion on results for planar graphs, we consider graphs of higher genus. In 2001, Schroeder conjectured that if a graph has genus $g$, then its cop number is at most $g + 3$. While Schroeder’s bound is known to hold for planar and toroidal graphs, the case for graphs with higher genus remains open. We consider the capture time of graphs on surfaces and examine results for embeddings of graphs on non-orientable surfaces. We present a conjecture by the second author, and in addition, we survey results for the lazy cop number, directed graphs, and Zombies and Survivors.

2010 Mathematics Subject Classification

05C10, 05C57

Full Text (PDF format)

The authors gratefully acknowledge support from NSERC.

The second author is also supported in part by the Canada Research Chairs program, and by the Research Grant P1-0297 of ARRS (Slovenia).

Received 22 April 2018

Published 27 September 2019