×

Meyniel’s conjecture on the cop number: a survey. (English) Zbl 1276.05074

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.

MSC:

05C57 Games on graphs (graph-theoretic aspects)
91A24 Positional games (pursuit and evasion, etc.)