Cops and robber in graphs with bounded vertex cover number
Abstract
Meyniel's conjecture states that $n$-vertex connected graphs have cop number $O(\sqrt{n})$. The current best known upper bound is $n/2^{(1-o(1))\sqrt{\log n}}$, proved independently by Lu and Peng (2011), and by Scott and Sudakov (2011). In this paper, we extend their result by showing that every connected graph with vertex cover number $k$ has cop number at most $k/2^{(1-o(1))\sqrt{\log k}}$. This is the first sublinear upper bound on the cop number in terms of the vertex cover number.
Fields of Study & Subjects
Advanced Graph Theory Research
Limits and Structures in Graph Theory
Complexity and Algorithms in Graphs
Publication details
- Journal / source
- arXiv (Cornell University)
- Publication date
- 7 February 2026
- Language
- EN
- Document type
- Preprint