Cops and Robbers on Graphs without Long or Short Holes
Abstract
In 2019, Sivaraman conjectured that every Pk-free graph has cop number at most k−3 for k≥ 5. Chudnovsky, Norin, Seymour, and Turcotte proved P5-free graphs have cop number at most $2$. For k≥ 6 Sivaraman's conjecture remains widely open. There is little evidence to believe Sivaraman's conjecture is optimal, making the discovery of substantially better bounds interesting, even for subclasses of Pk-free graphs. We consider this problem for graphs with no long holes, which generalizes Pk-free graphs, that also have some forbidden shorter holes. Specifically, we show that for t≥ 13, (C4,…, Ct, Ck,Ck+1,…)-free graphs have cop number at most ⌈ (k−2)/(⌊ t/4⌋ )⌉+1. Taking Ck−1, which has cop number $2$ whenever k≥ 5, demonstrates that this bound is tight up to a small constant factor for infinity many pairs k and t. The proof relies on showing that in graphs without short holes, the closed neighbourhood of a short induced path can be guarded by $1$ cop, even when these paths are not geodesics. Additionally, for t≥ 2 we show that (Ct+2,Ct+3,Ck, Ck+1,…, )-free graphs have cop number at most (t−1)⌈ ((k−2))/t⌉. This show that (C4,C5,Ck,Ck+1,…)-free graphs have cop number at most ⌈ (k−2)/2⌉, extending work by Clow and Meger on (Pk,claw, butterfly, C4,C5)-free graphs to a substantially more general class.
Related
- Improved bounds for the lazy cops and robbers on generalized hypercubes
- Fast robbers on abelian Cayley graphs and digraphs
- Strong isometric path complexity of graphs: Asymptotic minors, restricted holes, and graph operations
- Cops and Robber game in higher-dimensional manifolds with spherical and Euclidean metric
- Kerr black holes without primary hairs
BibTeX
@misc{clow2026cops,
title = {{Cops and Robbers on Graphs without Long or Short Holes}},
author = {Alexander Clow},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.36290},
eprint = {2610.36290},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.36290},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Cops and Robbers on Graphs without Long or Short Holes
AU - Alexander Clow
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.36290
UR - https://arxiv.org/abs/2610.36290
AB - In 2019, Sivaraman conjectured that every P_k-free graph has cop number at most k−3 for k≥ 5. Chudnovsky, Norin, Seymour, and Turcotte proved P_5-free graphs have cop number at most $2$. For k≥ 6 Sivaraman's conjecture remains widely open. There is little evidence to believe Sivaraman's conjecture is optimal, making the discovery of substantially better bounds interesting, even for subclasses of P_k-free graphs. We consider this problem for graphs with no long holes, which generalizes P_k-free graphs, that also have some forbidden shorter holes. Specifically, we show that for t≥ 13, (C_4,…, C_t, C_k,C_k+1,…)-free graphs have cop number at most ⌈ (k−2)/(⌊ t/4⌋ )⌉+1. Taking C_k−1, which has cop number $2$ whenever k≥ 5, demonstrates that this bound is tight up to a small constant factor for infinity many pairs k and t. The proof relies on showing that in graphs without short holes, the closed neighbourhood of a short induced path can be guarded by $1$ cop, even when these paths are not geodesics. Additionally, for t≥ 2 we show that (C_t+2,C_t+3,C_k, C_k+1,…, )-free graphs have cop number at most (t−1)⌈ ((k−2))/t⌉. This show that (C_4,C_5,C_k,C_k+1,…)-free graphs have cop number at most ⌈ (k−2)/2⌉, extending work by Clow and Meger on (P_k,claw, butterfly, C_4,C_5)-free graphs to a substantially more general class.
ER -