Cops and robber in graphs with bounded vertex cover number

Prosenjit Bose, Louis Esperet, Jędrzej Hodor, Gwenaël Joret, Piotr Micek, Clément Rambaud

arXivarxiv/2602.07435Feb 7, 2026math.COscore 0

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.

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2602.07435
curl -X POST /api/v1/records/arxiv/2602.07435/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2602.07435/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'