A new bound for the cops and robbers problem

In this short paper we study the game of cops and robbers, which is played on the vertices of some fixed graph $G$. Cops and a robber are allowed to move along the edges of $G$ and the goal of cops is to capture the robber. The cop number $c(G)$ of $G$ is the minimum number of cops required to win the game. Meyniel conjectured a long time ago that $O(\sqrt{n})$ cops are enough for any connected $G$ on $n$ vertices. Improving several previous results, we prove that the cop number of $n$-vertex graph is at most $n 2^{-(1+o(1))\sqrt{\log n}}$.

No reviews yet.

No comments yet.