ABSTRACT
Meyniel's conjecture is now a central topic in the fields of graph searching and Cops and Robbers. Meyniel's conjecture definitely stands out as one of the deepest problems on the cop number. Meyniel's conjecture was proved using the probabilistic method. This chapter summarizes some results on partial solutions of Meyniel's conjecture, especially those emphasizing random techniques. It provides the best currently known upper bound on c(n), and presents a proof due to Frieze, Krivelevich, and Loh using expansion and the probabilistic method. The chapter discusses the proof of Meyniel's conjecture for binomial random graphs and random d regular graphs. It also discusses families of graphs realizing the tightness of the Meyniel bound. Results for the two main random graph models, that are binomial and random regular graphs, support the conjecture regardless of the fact that there remains a large gap in the deterministic bounds; even the soft Meyniel's conjecture remains open.
