Meyniel's conjecture on the cop number: a survey (Q1937358)

Cops and Robbers is a game with certain rules which is played on a reflexive graph, i.e., each vertex has at least one loop. The cop number \(c(G)\) is the minimum number of cops required to win in the graph \(G\). Meyniel's conjecture says that \(c(G)=O(\sqrt{n})\) where \(n\) is the order of the graph \(G\). In this paper, the origins of this conjecture and recent developments of the problem are surveyed.