Cops and Robbers on Graphs with Path Constraints
Alexander Clow, Erin Meger · 2025
Read Cops and Robbers on Graphs with Path Constraints by Alexander Clow, Erin Meger (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-10941.txt.
Description
Alexander Clow and Erin Meger bound the difficulty of a graph pursuit game in this 2025 mathematics paper. In cops and robbers, a team of cops moves on a graph to catch a robber moving on the same graph. The cop number of a graph is the smallest team that can force a win. A 2019 conjecture says graphs with no long path as a subgraph need few cops.
The conjecture is settled only for short paths. Clow and Meger study graphs that avoid both a long path and a second small pattern called the E graph. For those, they prove a cop number bound that improves and extends an earlier claw-free result. They also give a general bound from a graph's longest path alone, sharpening a known estimate.
Catalog record
| CREATOR | Alexander Clow, Erin Meger |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-10941