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

CREATORAlexander Clow, Erin Meger
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE48 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-10941

Browse the full library · About the Tower of Babel