Journal of Combinatorics

Volume 3 (2012)

Number 2

Meyniel’s conjecture on the cop number: A survey

Pages: 225 – 238

DOI: https://dx.doi.org/10.4310/JOC.2012.v3.n2.a6

Authors

William Baird (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Anthony Bonato (Department of Mathematics, Ryerson University, Toronto, Ontario, Canada)

Abstract

Meyniel’s conjecture is one of the deepest open problems on the copnumber of a graph. It states that for a connected graph $G$ of order$n,$ $c(G) = O(\sqrt{n}).$ While largely ignored for over 20 years, theconjecture is receiving increasing attention. We survey the origins ofand recent developments towards the solution of the conjecture. Wepresent some new results on Meyniel extremal families containing graphsof order $n$ satisfying $c(G) \ge d\sqrt{n},$ where $d$ is a constant.

Keywords

cops and robbers, cop number, retract, random graph

Published 28 September 2012