Bounding the cop number of a graph by its genus
Nathan Bowler, Joshua Erde, Florian Lehner, Max Pitz
2021University of Birmingham Research Portal (University of Birmingham)12 citationsDOIOpen Access PDF
Abstract
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 .
Topics & Concepts
Bounding overwatchGenusCombinatoricsMathematicsGraphSubject (documents)Discrete mathematicsComputer scienceLibrary scienceArtificial intelligenceZoologyBiologyAdvanced Graph Theory ResearchArtificial Intelligence in Games