Meyniel's conjecture on the cop number
Cops and Robbers · Research workstream: problems/meyniels_conjecture/
Status partial high confidence
Meyniel's conjecture (c(G) ≤ C√n for every connected n-vertex graph) remains open. The best known general upper bound is n · 2^{-(1-o(1))√log₂ n}, proved independently by Lu–Peng (2012) and Scott–Sudakov (2011); the weak Meyniel conjecture (c(G) = O(n^{1−ε}) for some ε > 0) is also open for general graphs. Recent work has verified the full conjecture for dense large-girth graphs (minimum degree δ ≥ n^{2/g+ε}) and the weak form for algebraic graphs including Cayley sum and generalised Cayley graphs; a 2026 paper proves the hypergraph analogue c(H) = O(√(n/k)) for expanding hypergraphs and with high probability for random k-uniform hypergraphs under density conditions.
Cited literature (3)
-
Proves the weak Meyniel conjecture for Cayley sum graphs, generalised Cayley graphs, and twisted Cayley sum graphs by showing the cop number is at most twice the degree, with the bound combining with Bollobás–Janson–Riordan to yield c(G) = O(n^{1-ε}) for these families.
-
Establishes c(G) = O(n log(n)(δ−1)^{−⌊(g+1)/4⌋}) for graphs of girth g and minimum degree δ ≥ 2; verifies the full Meyniel conjecture when δ ≥ n^{2/g+ε}, and the weak form (c(G) = O(n^{1−α})) for girth g ≥ 7 with δ ≥ n^ε.
-
Proves the hypergraph Meyniel conjecture c(H) = O(√(n/k)) for expanding k-uniform hypergraphs and shows it holds with high probability for random H^k(n,p) when k ≥ log³n and the typical degree p·C(n−1,k−1) = ω(log³n); extends corpus record 2307.15512.
Reviewer notes. The full conjecture c(G) ≤ C√n for all connected n-vertex graphs remains open; the best general bound n · 2^{-(1-o(1))√log n} (Lu–Peng 2012; Scott–Sudakov 2011) predates this record. The weak Meyniel conjecture is also open in full generality. A paper arXiv:2311.13792 claiming progress for expanders was withdrawn. Corpus record 2602.07435 addresses a related but distinct parameter (vertex cover number k), giving c(G) ≤ k/2^{(1-o(1))√log k}. Author names for arXiv:2303.05381 and arXiv:2606.27066 were not returned by the WebFetch summaries and are marked '(see arXiv abstract)' to avoid fabrication. The 2026 hypergraph paper (2606.27066) complements corpus record 2307.15512 by handling random/expanding hypergraphs. The workstream's disproof-oriented approach is consistent with the conjecture remaining wide open.
Context
In the game of Cops and Robbers, $k$ cops choose vertices, then the robber chooses a vertex, and the two sides alternate moves (cops first), each piece moving to a vertex at distance at most one; the cops win if a cop occupies the robber's vertex. The cop number $c(G)$ is the least $k$ for which the cops have a winning strategy. Writing $c(n)$ for the maximum of $c(G)$ over connected graphs of order $n$, the conjecture says $c(n) = O(\sqrt{n})$; it is equivalent to $M_k = \Omega(k^2)$, where $M_k$ is the minimum order of a connected graph with cop number $k$ (Baird et al. 2014). The bound would be tight up to the constant: incidence graphs of projective planes give $c(n) \ge \sqrt{n/2} - o(\sqrt n)$.
Related records in this index
This conjecture was absent from the Open Problem Garden and arXiv corpora; the records below are the nearest ones.
- Sublinear cop number vs treedepth — cop number vs. treedepth, from the paper proving $c(G) \le k/2^{(1-o(1))\sqrt{\log k}}$ for vertex cover number $k$
- Cop number √(n/k) bound for k-uniform hypergraphs — hypergraph analogue $c(H) = O(\sqrt{n/k})$
- Sharpness of ¼g cop-number exponent — sharpness of the high-girth lower bound $\Omega((\delta-1)^{g/4})$
Editorial notes. Stated by Meyniel in a 1985 personal communication to Frankl and first published in P. Frankl, 'Cops and robbers in graphs with large girth and Cayley graphs', Discrete Appl. Math. 17 (1987). Not in the corpus before this record: Open Problem Garden has no Cops and Robbers page, and the arXiv-extracted records that cite the conjecture were matched against OPG and manually rejected. The workstream approaches the conjecture from the disproof side (what a counterexample would have to look like).
Source
problems/meyniels_conjecture — self-contained workstream in this repository
Original reference: P. Frankl, Cops and robbers in graphs with large girth and Cayley graphs, Discrete Applied Mathematics 17 (1987) 301–305.
https://github.com/graph-theory-AI/graph-conjectures/tree/main/problems/meyniels_conjecture