Meyniel’s conjecture on the cop number: A survey

By William Baird, Anthony Bonato. 2013

62 citations recorded by the source corpus.

Meyniel’s conjecture is one of the deepest open problems on the cop number of a graph. It states that for a connected graph G of order n, c(G) = O( √ n). While largely ignored for over 20 years, the conjecture is receiving increasing attention. We survey the origins of and recent developments towards the solution of the conjecture. We present some new results on Meyniel extremal families containing graphs of order n satisfying c(G) ≥ d√n, where d is a constant.

Subfields: Computational Theory and Mathematics, Geometry and Topology

View Paper: https://www.semanticscholar.org/paper/6149a5eef07093055207b4af75e99eee83417d71