The Cop Number of Graphs with Forbidden Induced Subgraphs

Mingrui Liu

Published 2019-08-29Version 1

In the game of Cops and Robber, a team of cops attempts to capture a robber on a graph $G$. Initially, all cops occupy some vertices in $G$ and the robber occupies another vertex. In each round, a cop can move to one of its neighbors or stay idle, after which the robber does the same. The robber is caught by a cop if the cop lands on the same vertex which is currently occupied by the robber. The minimum number of cops needed to guarantee capture of a robber on $G$ is called the {\em cop number} of $G$, denoted by $c(G)$. We say a family $\cal F$ of graphs is {\em cop-bounded} if there is a constant $M$ so that $c(G)\leq M$ for every graph $G\in \cal F$. Joret, Kamin\'nski, and Theis [Contrib. Discrete Math. 2010] proved that the class of all graphs not containing a graph $H$ as an induced subgraph is cop-bounded if and only if $H$ is a linear forest; morerover, $C(G)\leq k-2$ if if $G$ is induced-$P_k$-free for $k\geq 3$. In this paper, we consider the cop number of a family of graphs forbidding certain two graphs and generalized some previous results.