Improved Bounds on the Cop Number of a Graph Drawn on a Surface

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). It is conjectured by Schroder that \(c(G) \le 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) \le \frac{4g(G)}{3} + \frac{10}{3}\). Combining some of these ideas with some techniques introduced by Schroder we improve this bound and show that \(c(g) \le (1+o(1))(3- \sqrt{3}) g \approx 1.268 g\).
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    7
    References
    0
    Citations
    NaN
    KQI
    []