Cops and robbers on chess graphs

2025/09/23 by Ambrose, Sally, Evan Angelone, Angelone, Evan +11
Computer Science · Engineering · #05C57 #2020 MSC 49N75 (Primary) #91A24 (Secondary) #Advanced Graph Theory Research #Artificial Intelligence in Games #Combinatorics (math.CO) #FOS: Mathematics #Guidance and Control Systems

paper · pdf · doi:10.48550/arxiv.2509.18516

openalex publication_date 2025/09/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Cops and robbers is a pursuit-evasion game played on graphs. We completely classify the cop numbers for n × n knight graphs and queen graphs. This completes the classification of the cop numbers for all n × n classical chess graphs. As a corollary, we resolve an open problem about the monotonicity of c(Q_n). Moreover, we introduce royal graphs, a generalization of chess graphs for arbitrary piece movements, which models real-life movement constraints. We give results on the cop numbers for these families.

Citations

• Meyniel's conjecture on graphs of bounded degree
• Bounding the cop number of a graph by its genus
• Cops and Robbers is EXPTIME-complete

Related

• Cops and Robbers on Toroidal Chess Graphs
• The Cop Number of the One-Cop-Moves Game on Planar Graphs
• Cops and robbers on planar directed graphs
• A new bound for the cops and robbers problem
• On the Cop Number of String Graphs