{"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","summary":"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.","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-02-07","reactions":{}}