The Cops and Robber game on graphs with forbidden (induced) subgraphs

Abstract

The two-player, complete information game of Cops and Robber is played on undirected finite graphs. A number of cops and one robber are positioned on vertices and take turns in sliding along edges. The cops win if, after a move, a cop and the robber are on the same vertex. The minimum number of cops needed to catch the robber on a graph is called the cop number of that graph. In this paper, we study the cop number in the classes of graphs defined by forbidding one or more graphs as either subgraphs or induced subgraphs. In the case of a single forbidden graph we completely characterize (for both relations) the graphs which force bounded cop number. En passant, we bound the cop number in terms of tree-width.

Cited by in corpus (13)

• Cops that surround a robber
• Cops and robbers on directed and undirected abelian Cayley graphs
• Cops and Robbers on Graphs with a Set of Forbidden Induced Subgraphs
• Cops and robbers on $2K_2$-free graphs
• On the hat guessing number of a planar graph class
• Cops and Robber Game with a Fast Robber on Interval, Chordal, and Planar Graphs
• 4-cop-win graphs have at least 19 vertices
• Structure of (bull, diamond)-free graphs and its applications
• Cop number of graphs without long holes
• Cop number of $2K_2$-free graphs
• Constructing Geometric Graphs of Cop Number Three
• A note on bounds for the cop number using tree decompositions
• Improved bounds on the cop number when forbidding a minor