4-cop-win graphs have at least 19 vertices

2020/06/04 by Turcotte, Jérémie, Yvon, Samuel · 2 citations
#05C57 (Primary) 05C35 #05C85 #68V05 (Secondary) #90C35 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2006.02998

Abstract

We show that the cop number of any graph on 18 or fewer vertices is at most 3. This answers a question posed by Andreae in 1986, as well as more recently by Baird et al. We also find all 3-cop-win graphs on 11 vertices, narrow down the possible 4-cop-win graphs on 19 vertices and make some progress on finding the minimum order of 3-cop-win planar graphs.

Cited by

• Cops and Robbers on Graphs with Path Constraints
• 4K₁-free graph with the cop number 3

Related

• On the minimum order of k-cop-win graphs
• On the cop number of toroidal graphs
• Improved bounds on the cop number when forbidding a minor
• On Generalised Petersen Graphs of Girth 7 that have Cop Number 4
• Small Connected Planar Graph with 1-Cop-Move Number 4