Bounding the cop number of a graph by its genus
Nathan Bowler, Joshua Erde, Florian Lehner, Max F. Pitz · University of Birmingham Research Portal (University of Birmingham) · 2021
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). The best known bound, that c(G) ≤ ⌊ 3g(G) 2 ⌋ + 3, was given by Schroder, who conjectured that in fact c(G) ≤ g(G) + 3. We give the first improvement to Schroder's bound, showing that c(G) ≤ 4g(G) 3 + 10 3 .