Meyniel's conjecture on the cop number: a survey
classification
🧮 math.CO
keywords
conjecturemeynielgraphnumberordersqrtsurveyattention
read the original abstract
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(\sqrt{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) \ge d\sqrt{n},$ where $d$ is a constant.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.