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) \leq \left\lfloor \frac{3 g(G)}{2}\right\rfloor + 3$, was given by Schr\"{o}der, who conjectured that in fact $c(G) \leq g(G) + 3$. We give the first improvement to Schr\"{o}der's bound, showing that $c(G) \leq \frac{4g(G)}{3} + \frac{10}{3}$. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1137/20M1312150 | ACTA MATHEMATICA UNIVERSITATIS COMENIANAE |
Keywords | DocType | Volume |
cops and robbers, genus, pursuit games | Journal | 88 |
Issue | ISSN | Citations |
3 | 0231-6986 | 0 |
PageRank | References | Authors |
0.34 | 0 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Nathan Bowler | 1 | 16 | 6.83 |
Joshua Erde | 2 | 4 | 4.93 |
Florian Lehner | 3 | 21 | 7.24 |
Max Pitz | 4 | 1 | 4.75 |