Math Conjectures

Meyniel's Conjecture on the Cop Number

OPENMajorConjectureProposed 1985 · Standard version

Canonical statement

In the perfect-information game on a finite connected simple graph GG, the cops choose their starting vertices and the robber then chooses one. The sides alternate, beginning with the cops; on a cops' turn every cop may independently traverse one edge or stay fixed, and on a robber turn the robber may do the same. The cops win when a cop occupies the robber's vertex. If c(G)c(G) is the minimum number of cops having a winning strategy, then there is an absolute constant CC such that every nn-vertex GG satisfies
c(G)≤Cn. c(G)\leq C\sqrt n.
View source LaTeX
In the perfect-information game on a finite connected
simple graph \(G\), the cops choose their starting vertices and the
robber then chooses one. The sides alternate, beginning with the cops;
on a cops' turn every cop may independently traverse one edge or stay
fixed, and on a robber turn the robber may do the same. The cops win when
a cop occupies the robber's vertex. If \(c(G)\) is the minimum number of
cops having a winning strategy, then there is an absolute constant
\(C\) such that every \(n\)-vertex \(G\) satisfies
\[
  c(G)\leq C\sqrt n.
\]
GRAPH-021:[Frankl1987Cops][BonatoNowakowski2011][ScottSudakov2011Meyniel]
Graph theoryGame theory and mathematical economics

Notes

In the game of cops and robbers, several cops and one robber occupy vertices of a finite connected graph and move alternately along edges or stay in place, with perfect information; the cops win by occupying the robber's vertex. The cop number c(G)c(G) is the least number of cops guaranteeing a win. Meyniel conjectured in 1985 that there is an absolute constant CC with c(G)≤Cnc(G)\le C\sqrt n for every connected nn-vertex graph, a conjecture recorded in print in a paper of Frankl [Frankl1987Cops].

The conjectured order of magnitude cannot be improved, since known graph families require on the order of n\sqrt n cops. On the upper-bound side, Scott and Sudakov proved a new bound for the problem [ScottSudakov2011Meyniel], and the best universal upper bound now has the shape n1/2+o(1)n^{1/2+o(1)}, matching the conjecture up to the lower-order term in the exponent. The game and its surrounding theory are treated at length by Bonato and Nowakowski [BonatoNowakowski2011].

The conjecture remains open: what is missing is precisely the removal of the o(1)o(1) in the exponent, reaching a genuine constant times n\sqrt n.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.