Joshua Erde

Bounding the cop number of a graph by its genus

Cops and robbers is a pursuit game played on a graph where a group of Cops co-ordinate to catch a Robber. The Cop number of a graph c(G) is the minimum number of Cops needed to catch a robber.
A classic result Aigner and Fromme say that three Cops are sufficient to catch a Robber on any planar graph, that is, c(G) ≤ 3 for every planar G. This bound was extended to graphs drawn on general surfaces by Quillot, who showed that c(G) ≤ 2g(G) +3 where g(G) is the genus of G.

Schroeder gave a strategy which improves this bound to (3/2)g(G) + 3 and conjectured that the stronger bound g(G) + 3 should hold. We give the first improvement to Schroeder's bound, showing that c(G) ≤ (4/3)g +3.

Joint work with Nathan Bowler, Florian Lehner and Max Pitz.