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.
Reviewer: Arnfried Kemnitz (Braunschweig)
MSC:
05C57 | Games on graphs (graph-theoretic aspects) |
91A24 | Positional games (pursuit and evasion, etc.) |