Meyniel's conjecture on graphs of bounded degree

2019/12/15 by Hosseini, Seyyed Aliasghar, Mohar, Bojan, de la Maza, Sebastian Gonzalez Hermosillo · 3 citations
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.1912.06957

Abstract

The game of Cops and Robbers is a well known pursuit-evasion game played on graphs. It has been proved \citebounded_degree that cubic graphs can have arbitrarily large cop number c(G), but the known constructions show only that the set \c(G) | G cubic\ is unbounded. In this paper we prove that there are arbitrarily large subcubic graphs G whose cop number is at least n^1/2-o(1) where n=|V(G)|. We also show that proving Meyniel's conjecture for graphs of bounded degree implies a weak Meyniel's conjecture for all graphs.

Cited by

• Cop number of partial cubes
• Cops and robbers on chess graphs
• Pushing Cops and Robber on Graphs of Maximum Degree 4

Related

• Meyniel's conjecture holds for random graphs
• Meyniel's conjecture holds for random d-regular graphs
• Meyniel's conjecture on the cop number: a survey
• Expanders Satisfy the Weak Meyniel Conjecture
• A new bound for the cops and robbers problem