On Meyniel's conjecture of the cop number
Meyniel conjectured that the cop number c(G) of any connected graph G on n vertices is at most for some constant C. In this article, we prove Meyniel's conjecture in special cases that G has diameter 2 or G is a bipartite graph of diameter 3. For general connected graphs, we prove , improving the best previously known upper-bound O(n/ lnn) due to Chiniforooshan.
meyniel's conjecture cop number coprobber game