Id: arxiv/2602.07435 Url: https://arxiv.org/abs/2602.07435 Tags: math.CO, cs.DM Score: 0 Title: Cops and robber in graphs with bounded vertex cover number Domain: math.CO Source: arxiv Authors: Prosenjit Bose, Louis Esperet, Jędrzej Hodor, Gwenaël Joret, Piotr Micek, Clément Rambaud Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-02-07 Page: https://delphi.science/r/arxiv/2602.07435 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.