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\).
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
7
References
0
Citations
NaN
KQI