Improved bounds on the cop number of a graph drawn on a surface

Activity: Talk or presentationTalk at conference or symposiumScience to science


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)$. It is conjectured by Schr\"{o}der that $c(G) \leq g(G) + 3$. Recently, by relating this problem to a topological game, the authors, together with Bowler and Pitz, gave the current best known bound that $c(G) \leq \frac{4g(G)}{3} + \frac{10}{3}$. Combining some of these ideas with some techniques introduced by Schr\"{o}der we improve this bound and show that $c(g) \leq (1+o(1))(3- \sqrt{3}) g \approx 1.268 g$.
Period6 Sept 2021
Event titleEuropean Conference on Combinatorics, Graph Theory and Applications: EuroComb 2021
Event typeConference
LocationVirtual, Barcelona, SpainShow on map
Degree of RecognitionInternational