Cops and Robbers on Graphs without Long or Short Holes
math.CO
Submitted: 2026-10-26
Updated: 2026-10-26
Comments: 23 Pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: In 2019, Sivaraman conjectured that every P k-free graph has cop number at most k-3 for k at least 5.
Abstract
In 2019, Sivaraman conjectured that every P k-free graph has cop number at most k-3 for k at least 5. Chudnovsky, Norin, Seymour, and Turcotte proved P 5-free graphs have cop number at most 2. For k at least 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 at least 13, (C 4,, C t, C k,C k+1,) -free graphs have cop number at most k-2 over t over 4 +1. Taking C k-1, which has cop number 2 whenever k at least 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 at least 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) over t. This show that (C 4,C 5,C k,C k+1,) -free graphs have cop number at most k-2 over 2, extending work by Clow and Meger on (P k, claw, butterfly, C 4,C 5) -free graphs to a substantially more general class.
Related papers
- Three-ends Furstenberg estimates and approximate rectangles
- Multicolor Ramsey numbers of ordered matchings
- Exponential random graph models with soft clique constraints
- A Full-Sequence Quantitative Gap Between the Chromatic and Cochromatic Numbers of a Random Graph
- Ehrhart positivity for paving positroids
- Nonlinear lower-tail large deviations at criticality