6
$\begingroup$

I am following Schroeder's work on pursuit-evasion games on graphs (often called "cops and robbers"). In his 2001 publication ("The copnumber of a graph is bounded by $\lfloor 3/2 {\ \rm genus}(G)+3\rfloor$". In: Categorical perspectives (Kent, OH, 1998). Trends in Mathematics, pp. 243-263. Birkhäuser, Boston 2001) he derived an upper bound for the cop number $c(G)$ that depends on the genus $g$ of the surface on which the graph $G$ can be embedded: $c(G)\leq \lfloor 3g/2 +3\rfloor$. My most recent reference for this result is "Topological directions in Cops and Robbers" from 2018, Anthony Bonato and Bojan Mohar, arXiv:1709.09050v2 .

This gives $c(G)\leq 4$ if $G$ can be embedded on a torus. Now, I have worked extensively to come up with an example of a graph $G$ that actually hits this bound, i.e. I have searched for $G$ with $c(G)=4$, but with no success. So I am starting to see strong evidence for the conjecture $c(G)\leq 3$ if $G$ can be embedded on a torus. Question: Is someone aware of a more recent reference for this conjecture? It appears lower than any other bound I have seen in the literature so far (N.B. I would also be interested in references beyond torus embeddings)

$\endgroup$

1 Answer 1

7
$\begingroup$

What you conjecture has been conjectured (more or less explicitly) a few times before. In the paper by Bonato and Mohar that you reference, it is dubbed the Andreae-Schroeder conjecture.

I recently proved that it is true, i.e. the cop-number of toroidal graphs is at most 3, see this ArXiv preprint. See also this preprint, where a general bound $c(G) \leq \frac{4g}{3} + \frac {10}3$ is proved.

$\endgroup$
1
  • 1
    $\begingroup$ I am very impressed by your result, just took a first look. Your second reference with the general bound is amazing: extremely close to the original Schroeder $g+3$ conjecture!! $\endgroup$
    – soerenssen
    Jul 31, 2020 at 6:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.