# Cops and robber on subclasses of $P_{5}$-free graphs

1Uttam K. Gupta, 2Suchismita Mishra, 1Dinabandhu Pradhan

1Department of Mathematics & Computing
Indian Institute of Technology (ISM), Dhanbad

2 Department of Mathematics, Universidad Andrés Bello, Chile
Email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Corresponding author.

###### Abstract

The game of cops and robber is a turn based vertex pursuit game played on a
connected graph between a team of cops and a single robber. The cops and the
robber move alternately along the edges of the graph. We say the team of cops
win the game if a cop and the robber are at the same vertex of the graph. The
minimum number of cops required to win in each component of a graph is called
the cop number of the graph. Sivaraman [Discrete Math. 342(2019), pp.
2306-2307] conjectured that for every $t\geq 5$, the cop number of a connected
$P_{t}$-free graph is at most $t-3$, where $P_{t}$ denotes a path on $t$
vertices. Turcotte [Discrete Math. 345 (2022), pp. 112660] showed that the cop
number of any $2K_{2}$-free graph is at most $2$, which was earlier
conjectured by Sivaraman and Testa. Note that if a connected graph is
$2K_{2}$-free, then it is also $P_{5}$-free. Liu showed that the cop number of
a connected ($P_{t}$, $H$)-free graph is at most $t-3$, where $H$ is a cycle
of length at most $t$ or a claw. So the conjecture of Sivaraman is true for
($P_{5}$, $H$)-free graphs, where $H$ is a cycle of length at most $5$ or a
claw. In this paper, we show that the cop number of a connected
($P_{5},H$)-free graph is at most $2$, where $H\in\\{C_{4}$, $C_{5}$, diamond,
paw, $K_{4}$, $2K_{1}\cup K_{2}$, $K_{3}\cup K_{1}$, $P_{3}\cup P_{1}\\}$.

Keywords: Cops and Robber; cop number; forbidden induced subgraphs;
$P_{5}$-free graphs.

##  1 Introduction

All the graphs in this paper are finite, simple, and undirected. The complete
graph, cycle, and path on $n$ vertices are denoted by $K_{n},C_{n}$, and
$P_{n}$, respectively. The _disjoint union_ of two vertex-disjoint graphs $G$
and $H$, denoted by $G\cup H$, is the graph with vertex set $V(G)\cup V(H)$
and edge set $E(G)\cup E(H)$. For a positive integer $r$, $rG$ denotes the
disjoint union of $r$ copies of $G$. The game of cops and robber was
introduced by Quilliot [19] in 1978 and independently by Nowakowski and
Winkler [14] in 1981. The game is played on a connected graph by a team of
cops and a robber. In the first turn, all the cops are placed on the vertices
of the graph (multiple cops can be placed on a single vertex). In the second
turn, the robber chooses a vertex. Then the cops and the robber take their
moves in alternative turns, starting with the cops. A valid move for a cop is
to stay at its current position or to move to an adjacent vertex. A valid move
for the robber is similar to the cops. A _round_ of moves consists of two
consecutive turns in which the cops have the first turn and then the robber
has its turn. We say that a cop captures the robber if both of them are on the
same vertex of the graph. The cops win if after a finite number of rounds, one
of the cops captures the robber. The robber wins if the cops cannot win in a
finite number of rounds. The _cop number_ of a graph $G$, denoted by $cop(G)$,
is defined as the minimum number of cops required such that the cops win in
each component of $G$.

The characterization of graphs with the cop number one was studied by Quilliot
[19] and independently by Nowakowski and Winkler [14]. The study of graphs
with higher cop number was initiated by Aigner and Fromme [1]. Several
characterizations of graphs with cop number $k$ have been studied by Clarke
and MacGillivray [6]. Berarducci and Intrigila [4] gave an
$O(n^{O(k)})$-algorithm to decide whether $cop(G)\leq k$ for a $n$-vertex
graph $G$. Fomin et al. [7] showed that it is NP-hard to determine the cop
number of a graph. Moreover, it is $W[2]$-hard to determine whether
$cop(G)\leq k$, where $k$ is the parameter [7]. Meyniel conjectured that the
cop number of a connected graph on $n$ vertices is at most $O(\sqrt{n})$. The
conjecture was made by Meyniel in a personal communication with Frankl in
$1985$ and is mentioned in [8]. Frankl showed that $cop(G)=o(n)$ for any
connected $n$-vertex graph $G$. One can ask whether there exists $\epsilon>0$
such that the cop number of any connected $n$-vertex graph $G$ is
$O(n^{1-\epsilon})$? This problem is also open. For more details, see the
survey by Baird and Bonato [3]. The best known upper bound on the cop number
of a graph on $n$ vertices is $n2^{-(1+o(1))\sqrt{\log_{2}n}}$ (see [12, 15]).
Lu and Peng [12] showed that if $G$ is a graph of diameter at most $2$ or a
bipartite graph of diameter at most $3$, then $cop(G)\leq 2\sqrt{n}-1$; thus
validating the Meyniel’s conjecture for such graphs. Later, Wagner [20]
improved the result of Lu and Peng on the same class of graphs by showing that
such graphs satisfy $cop(G)\leq\sqrt{2n}$. Lu and Peng used random arguments
to prove the bound whereas Wagner’s proof did not include randomness.

The cop number of a family of graphs $\mathcal{G}$ is the minimum integer $k$
such that $cop(G)\leq k$ for any graph $G$ in $\mathcal{G}$. If we cannot find
such an integer $k$, then we say $\mathcal{G}$ is a family with unbounded cop
number (or the cop number of $\mathcal{G}$ is not bounded). Aigner and Fromme
[1] proved that the cop number of a graph with girth $\ell$ is at least its
minimum degree, when $\ell>4$. Thus the cop number of the class of all graphs
is not bouned. Andreae [2] showed the cop number of the class of all
$d$-regular graphs is not bounded. Aigner and Fromme [1] proved that the cop
number of the class of all planar graph is $3$. Moreover, dodecahedron is a
planar graph whose cop number is $3$. Clarke [5] proved that the cop number of
any outerplanar graph is at most $2$. The cop number of the class of all
$k$-chordal graphs is at most $k-1$ [10].

Let $\mathcal{F}$ be a family of graphs. A graph $G$ is said to be
$\mathcal{F}$-free if no $H\in\mathcal{F}$ is isomorphic to an induced
subgraph of the graph $G$. When $\mathcal{F}=\\{H\\}$ (resp.
$\\{H_{1},H_{2},\ldots,H_{k}\\}$, $k\geq 2$), we use $H$-free (resp.
$(H_{1},H_{2},\ldots,H_{k})$-free) graphs to denote the $\mathcal{F}$-free
graphs. Joret et al. [9] proved that the cop number of the class of $H$-free
graphs is bounded if and only if every component of $H$ is a path.
Furthermore, suppose that $\mathcal{G}$ be a family of graphs such that the
diameter of any $G\in\mathcal{G}$ is at most $k$ for some natural number $k$.
Masjoodi and Stacho [13] showed that the class of all $\mathcal{G}$-free
graphs has bounded cop number if and only if $\mathcal{G}$ contains a path or
$\mathcal{G}$ contains a generalized claw and a generalized net. It is known
that the cop number of a connected $P_{t}$-free graphs is at most $t-2$ [9].
Sivaraman [16] gave a shorter proof for the same by using Gyárfás path
argument, where he conjectured the following.

######  Conjecture 1.1 ([16]).

The cop number of a connected $P_{t}$-free graph is at most $t-3$ for $t\geq
5$.

Conjecture 1.1 was verified for a subclass of $P_{t}$-free graphs; the class
of ($P_{t},C_{\ell}$)-free graphs, where $t\geq 5$ and $3\leq\ell\leq t$ [11].
It is known that the cop number of a $P_{4}$-free graph is at most $2$ [9].
Note that if a graph is $2K_{2}$-free, then it is also $P_{5}$-free. Sivaraman
and Testa [17] showed that the cop number of a connected $2K_{2}$-free graph
$G$ is at most $2$ if the diameter of $G$ is $3$ or it is $C_{\ell}$-free for
some $\ell\in\\{3,4,5\\}$. In the same paper, they conjectured that the class
of $2K_{2}$-free graphs has cop number $2$. Later, this conjecture was proved
by Turcotte [18].

###  1.1 Our results

Liu [11] showed that the cop number of a connected ($P_{t},H$)-free graph is
at most $t-3$, where $t\geq 5$ and $H$ is a cycle of length at most $t$ or a
claw. First we give a short proof for these results for the case $t=5$ by
using Gyárfás path argument (see Lemma 2.1 of Section 2). Then by using that,
we find the cop number of different subclasses of $P_{5}$-free graphs. In
Section 3, we first show that the cop number of a connected ($P_{5}$,
paw)-free graph is at most $2$. So if a ($P_{5},K_{4}$)-free graph is also
paw-free, then its cop number is at most $2$. We study the structure of a
connected ($P_{5},K_{4}$)-free graph, that has an induced paw, around an
induced paw. By using the structural properties, we show that the cop number
of a connected ($P_{5},K_{4}$)-free graph is at most $2$ in Section 3. We show
that the cop number of every connected ($P_{5},K_{3}\cup K_{1})$-free graph
and every connected $P_{3}\cup P_{1}$-free graph is at most $2$ in Section 4
and Section 5, respectively. In Section 6, we show that the cop number of
every connected ($P_{5}$, diamond)-free graph and every connected
$(P_{5},2K_{1}\cup K_{2})$-free graph is at most $2$. We prove these results
by showing the non-existence of any minimum counterexample. Again, $C_{4}$ and
$C_{5}$ are $(P_{4},P_{3}\cup P_{1},2K_{2})$-free and ($P_{5},K_{4}$, diamond,
paw, $C_{4}$, claw, $K_{3}\cup K_{1},2K_{1}\cup K_{2}$)-free graphs,
respectively with the cop number $2$. Therefore, the cop number of the class
of ($P_{5},H$)-free graphs is $2$, where $H$ is a graph on $4$ vertices and
has at least one edge.

##  2 Notations, terminologies, and preliminary results

Let $G$ be a graph and $x$ be a vertex of $G$. The _neighborhood_ of $x$ in
$G$, denoted by $N(x)$, is the set of all the neighbors of $x$ in $G$. The
_closed neighborhood_ of $x$ in $G$, denoted by $N[x]$, is the set
$\\{x\\}\cup N(x)$. For a set $S\in V(G)$, we define $N(S)=\\{v\in
V(G)\setminus S\mid N(v)\cap S\neq\emptyset\\}$ and $N[S]=S\cup N(S)$. A set
$D\subseteq V(G)$ is called a _dominating set_ of $G$ if $N[D]=V(G)$. For two
disjoint sets of vertices $S$ and $T$, $[S,T]$ denotes the set $\\{xy\in
E(G)\mid x\in S,y\in T\\}$. We say that $[S,T]$ is _complete_ if every vertex
in $S$ is adjacent to every vertex of $T$ in $G$. For a set of vertices $S$,
$G[S]$ and $G-S$ denote the subgraphs induced by $S$ and $V(G)\setminus S$ in
$G$, respectively. The length of a path is the number of edges in it. The
distance of a vertex $u$ from a set $S$ is the least length of $u-v$ paths for
every vertex $v\in S$. We use Cop $1$ and Cop $2$ as the names of the two cops
throughout the paper. We refer to Figure 1 for some special graphs mentioned
in this paper.

Figure 1: Some special graphs

Recall that in the game of cops and robber, a _round_ of moves consists of two
consecutive turns in which the cops have the first turn and then the robber
has its turn. Moreover, a cop captures the robber if they are at the same
vertex of the graph. This happens only if in the robber’s turn, the robber
stays or moves to a position that belongs to the closed neighborhood of the
position of one of the cops. Equivalently, we can say that a cop at $x$
captures the robber at $y$ if after any round of moves of the cops and the
robber, we have $y\in N[x]$.

Liu [11] proved that the cop number of any connected $(P_{t},C_{\ell})$-free
graph is at most $t-3$ for any natural number $t\geq 5$ and $\ell\leq t$.
Moreover, it also has been shown that the cop number of a connected ($P_{t}$,
claw)-free graph is at most $t-3$ for $t\geq 5$. To make the paper self-
contained, we prove these results for $t=5$.

######  Lemma 2.1 ([11]).

Let $G$ be a connected $(P_{5},H)$-free graph, where
$H\in\\{C_{3},C_{4},C_{5},$ claw$\\}$. Then $cop(G)\leq 2$.

###### Proof.

We prove the lemma by arguing that two cops capture the robber after a finite
number of turns. Let $v_{1}$ be a vertex of $G$. In the first turn, we place
both the cops at $v_{1}$. To avoid immediate capture, the robber must choose a
vertex $y$ that is not a neighbor of $v_{1}$. Let $X$ be the component of the
graph induced by $V(G)\setminus N[v_{1}]$ such that $y\in X$. Since $G$ is
connected, we have $N(v_{1})\cap N(X)\neq\emptyset$. In the next turn, Cop $1$
stays at $v_{1}$ and Cop $2$ moves to a vertex $v_{2}\in N(v_{1})\cap N(X)$.
If the robber moves to a vertex of $N(v_{1})$, then the cop at $v_{1}$
captures the robber. So to avoid capture, the robber should stay in $X$. Let
the robber choose $x\in N[y]\cap X$ as its position. If $x$ is a neighbor of
$v_{2}$, then the robber gets captured by Cop $2$. So we may assume that $x$
is at distance at least $2$ from $v_{2}$. Since $v_{2}$ has a neighbor in $X$
and $X$ is a component of the graph induced by $V(G)\setminus N[v_{1}]$, there
exists an induced path $P$ between $v_{2}$ and $x$ of length at least $2$ such
that $V(P)\setminus\\{v_{2}\\}\subseteq V(X)$. This implies that
$V(P)\cup\\{v_{1}\\}$ induces a path of length at least $3$. Since $G$ is
$P_{5}$-free, the length of the path induced by $V(P)\cup\\{v_{1}\\}$ is $3$.
This implies that $v_{2}$ is at distance $2$ from $x$. Let $v_{3}\in V(P)\cap
X$ be a common neighbor of $v_{2}$ and $x$. Note that
$\\{v_{1},v_{2},v_{3},x\\}$ induces a $P_{4}$ in $G$. Define $S:=\\{u\in
V(G)\mid N(u)\cap\\{v_{1},v_{2},v_{3},x\\}=\\{v_{1},x\\}\\}$ and $T:=\\{u\in
V(G)\setminus\\{v_{3}\\}\mid
N(u)\cap\\{v_{1},v_{2},v_{3},x\\}=\\{v_{2},x\\}\\}$.

We first prove that if $S=\emptyset$ or $T=\emptyset$, then $cop(G)\leq 2$.
Suppose that $S=\emptyset$. Then in the next turn, Cop $1$ and Cop $2$ move to
$v_{2}$ and $v_{3}$, respectively. To avoid immediate capture, the robber must
move. Suppose that the robber moves to a vertex $r$. Since $S=\emptyset$ and
$\\{v_{1},v_{2},v_{3},x,r\\}$ does not induce a $P_{5}$, $r$ is adjacent to
$v_{2}$ or $v_{3}$. Hence the robber gets captured by Cop $1$ or Cop $2$
implying that $cop(G)\leq 2$. Now suppose that $T=\emptyset$. In the next
turn, Cop $1$ stays at $v_{1}$ and Cop $2$ moves to $v_{3}$, respectively. To
avoid immediate capture, the robber must move to a vertex $r$. Since
$T=\emptyset$ and $\\{v_{1},v_{2},v_{3},x,r\\}$ does not induce a $P_{5}$, $r$
is adjacent to $v_{1}$ or $v_{3}$. Hence the robber gets captured by Cop $1$
or Cop $2$ implying that $cop(G)\leq 2$. Note that if $H\in\\{C_{4},$
claw$\\}$, then $T=\emptyset$. Again note that if $H=C_{5}$, then
$S=\emptyset$. So $cop(G)\leq 2$ if $H\in\\{C_{4},C_{5},$ claw$\\}$.

Now assume that $S\neq\emptyset$ and $T\neq\emptyset$. Then it is clear that
$H=C_{3}$. Let $s$ be a vertex of $S$. In the next turn, Cop $1$ stays at
$v_{1}$ and Cop $2$ moves to $v_{3}$. To avoid immediate capture, the robber
must move to a vertex $r$ that is not adjacent to $v_{1}$ and $v_{3}$. Note
that $r\in T$; otherwise $\\{v_{1},v_{2},v_{3},x,r\\}$ induces a $P_{5}$.
Again, $r$ is not adjacent to $s$; otherwise $\\{s,x,r\\}$ induces a $C_{3}$.
In the next turn, Cop $1$ moves to $v_{2}$ and Cop $2$ stays at $v_{3}$. To
avoid immediate capture, the robber must move to a vertex $r^{\prime}$ that is
not adjacent to $v_{2}$ and $v_{3}$. Since $\\{r^{\prime},r,x\\}$ does not
induce a $C_{3}$, $r^{\prime}$ is not adjacent to $x$. Again since
$\\{s,v_{1},v_{2},r,r^{\prime}\\}$ does not induce a $P_{5}$, $r^{\prime}$ is
adjacent to $s$ or $v_{1}$. If $r^{\prime}$ is adjacent to $s$, then
$\\{r^{\prime},s,x,v_{3},v_{2}\\}$ induces a $P_{5}$ which is a contradiction.
So $r^{\prime}$ is adjacent to $v_{1}$. Now
$\\{r^{\prime},v_{1},v_{2},v_{3},x\\}$ induces a $P_{5}$, again a
contradiction. So such a vertex $r^{\prime}$ does not exist. Hence the robber
cannot escape from $r$ and gets captured implying that $cop(G)\leq 2$.∎

Note that by Lemma 2.1, every $(P_{5},C_{4})$-free graph has the cop number at
most $2$. A more careful observation on the proof of Lemma 2.1 leads to a
result on a superclass of the class of $(P_{5},C_{4})$-free graphs. Note that
in the proof of Lemma 2.1, if $T\neq\emptyset$, then for any $t\in T$,
$\\{v_{1},v_{2},v_{3},x,t\\}$ induces a banner in $G$. So the following
corollary holds.

######  Corollary 2.2.

Let $G$ be a connected $(P_{5},$ banner$)$-free graph. Then $cop(G)\leq 2$.

We now conclude this section by describing a partition around an induced paw
of a graph to use that later. The partition is described as follows.

  * •

partition around an induced paw: Let $G$ be a graph and $P$ induce a paw in
$G$ with vertex set $P=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and edge set
$\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{2}v_{4}\\}$. Define the following
sets.

$\begin{array}[]{ll}A_{i}:=&\\{v\in N(P)\mid N(v)\cap P=\\{v_{i}\\}\\},1\leq
i\leq 4\\\ B_{ij}:=&\\{v\in N(P)\mid N(v)\cap P=\\{v_{i},v_{j}\\}\\},1\leq
i<j\leq 4\\\ T_{i}:=&\\{v\in N(P)\mid N(v)\cap
P=P\setminus\\{v_{i}\\}\\},1\leq i\leq 4\\\ D:=&\\{v\in N(P)\mid P\subseteq
N(v)\\}\\\ X:=&V(G)\setminus(P\cup N(P))\end{array}$

Let $A=\bigcup\limits_{1\leq i\leq 4}A_{i}$, $B=\bigcup\limits_{1\leq i<j\leq
4}B_{ij}$ and $T=\bigcup\limits_{1\leq i\leq 4}T_{i}$. Note that
$(A,B,D,P,T,X)$ is partition of $V(G)$ when the structure of $G$ is considered
around an induced paw.

##  3 On the class of ($P_{5}$, paw)-free graphs and ($P_{5},K_{4}$)-free
graphs

In this section, we first show that the cop number of a $(P_{5}$, paw$)$-free
graph is at most $2$ (Lemma 3.1). Then we use this result to show that the cop
number of any connected ($P_{5},K_{4}$)-free graph $G$ is at most $2$. The
idea of the proof is as follows. If $G$ is paw-free, then by Lemma 3.1,
$cop(G)\leq 2$. If $G$ contains an induced paw, then we consider the presence
of an induced co-banner in $G$. If $G$ contains an induced co-banner, then we
consider the partition of $V(G)$ as defined in • ‣ 2 around the paw contained
in an induced co-banner of $G$. Then we have $A_{1}\neq\emptyset$ which help
us to prove that the robber gets captured by two cops (Lemma 3.4). On the
other hand, if $G$ is co-banner-free, then we consider the presence of an
induced butterfly in $G$. If $G$ contains an induced butterfly, then we
consider the partition of $V(G)$ as defined in • ‣ 2 around a paw contained in
an induced butterfly of $G$. Then we have $B_{12}\neq\emptyset$ which help us
to prove that the robber gets captured by two cops (Lemma 3.5). If $G$ is
butterfly-free, then we consider the partition of $V(G)$ as defined in • ‣ 2
around any induced paw of $G$. Since $G$ is (co-banner, butterfly)-free, we
have $A_{1}=B_{12}=\emptyset$. In fact, the intuition of the proof is to
gradually prove that $A_{1}=B_{12}=\emptyset$ while taking the stronger
hypothesis that $G$ is co-banner-free and butterfly-free. Finally we show that
the robber gets captured by two cops (Lemma 3.8).

######  Lemma 3.1.

Let $G$ be a connected $(P_{5},paw)$-free graph. Then $cop(G)\leq 2$.

###### Proof.

If $G$ is $C_{3}$-free, then by Lemma 2.1, $cop(G)\leq 2$. So we may assume
that $G$ contains a $C_{3}$, say with vertex set $K=\\{u_{1},u_{2},u_{3}\\}$.
If for any vertex $x\in N(K)$, $|N(x)\cap K|=1$, then $K\cup\\{x\\}$ induces a
paw, a contradiction. So every vertex of $N(K)$ is adjacent to at least two
vertices of $K$. Now we show that every vertex of $G$ has a neighbor in $K$.
If possible, then let $y$ be a vertex at distance $2$ from $K$. Let $w$ be a
neighbor of $y$ in $N(K)$. Now since $w\in N(K)$, $w$ is adjacent to at least
two vertices of $K$. Without loss of generality, we may assume that $w$ is
adjacent to $u_{1}$ and $u_{2}$. Then $\\{u_{1},u_{2},w,y\\}$ induces a paw, a
contradiction. So we may conclude that such a vertex $y$ does not exist. Thus
no vertex of $G$ is at distance $2$ from $K$. Since $G$ is connected, every
vertex of $G$ has a neighbor in $K$. Notice that $\\{u_{1},u_{2}\\}$ is a
dominating set of $G$. Therefore, $cop(G)\leq 2$. ∎

Let $G$ be a connected $(P_{5},K_{4})$-free graph containing an induced paw,
say with vertex set $P=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and edge set
$\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{2}v_{4}\\}$. Define sets
$A_{i},B_{ij},T_{i},D,$ and $X$ around $P$ as defined in • ‣ 2 for every
$1\leq i,j\leq 4$ and $i<j$. Since $G$ is $K_{4}$-free, it can be noticed that
$T_{1}=D=\emptyset$. So we have the following observation.

######  Observation 3.2.

$T_{1}=D=\emptyset$.

######  Observation 3.3.

The following hold.

  1. (a)

$N(X)\cap N(P)\subseteq A_{2}\cup B_{12}\cup B_{23}\cup B_{24}\cup T_{2}\cup
T_{3}\cup T_{4}$.

  2. (b)

For any vertex $v\in N(P)$ and any component $H$ of $G[X]$, either
$[\\{v\\},V(H)]$ is complete or $[\\{v\\},V(H)]=\emptyset$.

  3. (c)

Every vertex in $X$ is at distance $2$ from $P$.

###### Proof.

(a) Let $u$ be an arbitrary vertex of $N(X)\cap N(P)$ and $x$ be a neighbor of
$u$ in $X$. Since $\\{x,u,v_{1},v_{2},v_{3}\\}$ does not induce a $P_{5}$,
$u\notin A_{1}\cup A_{3}\cup B_{14}\cup B_{34}$. Again since
$\\{x,u,v_{4},v_{2},v_{1}\\}$ does not induce a $P_{5}$, we have $u\notin
A_{4}\cup B_{13}$. By Observation 3.2, $T_{1}=D=\emptyset$. Therefore, $u\in
A_{2}\cup B_{12}\cup B_{23}\cup B_{24}\cup T_{2}\cup T_{3}\cup T_{4}$. Since
$u$ is an arbitrary vertex of $N(X)\cap N(P)$, (a) holds.

(b) If $[\\{v\\},V(H)]=\emptyset$, then we are done. Suppose that
$[\\{v\\},V(H)]\neq\emptyset$. Let $x$ be a neighbor of $v$ in $H$. First we
show that $v$ is adjacent to every vertex of $N(x)\cap X$. For the sake of
contradiction, let $x^{\prime}\in N(x)\cap X$ such that $x^{\prime}$ is not
adjacent to $v$. Since $v\in N(X)\cap N(P)$, by (a), $v\in A_{2}\cup
B_{12}\cup B_{23}\cup B_{24}\cup T_{2}\cup T_{3}\cup T_{4}$. Note that there
exist distinct vertices $v_{i},v_{j}\in P$ for $i,j\in\\{1,2,3,4\\}$ such that
$vv_{i},v_{i}v_{j}\in E(G)$ and $vv_{j}\notin E(G)$. Then
$\\{v_{j},v_{i},v,x,x^{\prime}\\}$ induces a $P_{5}$, a contradiction. So $v$
is adjacent to every vertex of $N(x)\cap X$. Now we show that $v$ is adjacent
to every vertex of $H$. Let $y$ be an arbitrary vertex of
$V(H)\setminus\\{x\\}$. If $y$ is adjacent to $x$, then, since $v$ is adjacent
to every vertex of $N(x)\cap X$, $v$ is adjacent to $y$. If $y$ is not
adjacent to $x$, then let $xx_{1}x_{2}\ldots x_{k}y;k\geq 1$ be an induced
path between $x$ and $y$ in $H$. By our argument, we have that $v$ is adjacent
to $x_{1}$. Again by our argument for $x_{1}$, we have that $v$ is adjacent to
$x_{2}$. Following this way, we conclude that $v$ is adjacent to $y$. Now
since $y$ is an arbitrary vertex of $V(H)\setminus\\{x\\}$, $v$ is adjacent to
every vertex of $H$. Thus (b) holds.

(c) Let $H$ be a component of $G[X]$. Since $G$ is connected, we have
$N(V(H))\cap N(P)\neq\emptyset$. Let $v\in N(V(H))\cap N(P)$. By (b), every
vertex of $H$ is adjacent to $v$. This implies that every vertex of $H$ is at
distance $2$ from $P$. Since $H$ is an arbitrary component of $G[X]$, (c)
holds. ∎

In the following lemma, we show that the cop number of a connected
($P_{5},K_{4}$)-free graph that has an induced co-banner is at most $2$.

######  Lemma 3.4.

Let $G$ be a connected $(P_{5},K_{4})$-free graph. If $G$ has an induced co-
banner, then $cop(G)\leq 2$.

###### Proof.

Suppose that $\\{a_{1},v_{1},v_{2},v_{3},v_{4}\\}$ induces a co-banner in $G$
with edge set $\\{a_{1}v_{1},v_{1}v_{2},v_{2}v_{3},$
$v_{3}v_{4},v_{4}v_{2}\\}$. Note that $P=\\{v_{1},v_{2},v_{3},v_{4}\\}$
induces a paw in $G$. Define the sets $A_{i},B_{ij},T_{i},D$, and $X$ around
$P$ as defined in • ‣ 2 for every $1\leq i,j\leq 4$ and $i<j$. Note that
$a_{1}\in A_{1}$. Again, $A_{3}=\emptyset$; otherwise for any $u\in A_{3}$,
either $\\{a_{1},v_{1},v_{2},v_{3},u\\}$ or $\\{u,a_{1},v_{1},v_{2},v_{4}\\}$
induces a $P_{5}$. Similarly, we can show that $A_{4}=\emptyset$. In the first
turn, we place Cop $1$ and Cop $2$ at $v_{1}$ and $v_{2}$, respectively. To
avoid immediate capture, the robber should choose a vertex $x$ that is not
adjacent to $v_{1}$ and $v_{2}$. Since $A_{3}=A_{4}=\emptyset$, we have $x\in
B_{34}\cup X$. To proceed further, we first prove a series of claims.

######  Claim 1.

$N(X)\cap N(P)\subseteq A_{2}\cup B_{12}\cup T_{2}\cup T_{3}\cup T_{4}$.

###### Proof of Claim 1.

Let $u$ be an arbitrary vertex of $N(X)\cap N(P)$ and $w\in X$ be a neighbor
of $u$. By Observation 3.3(a), $a_{1}$ has no neighbor in $X$. In particular,
$a_{1}$ is not adjacent to $w$. Now if $u\in B_{23}\cup B_{24}$, then either
$\\{a_{1},v_{1},v_{2},u,w\\}$ or $\\{v_{3},v_{4},u,a_{1},v_{1}\\}$ induces a
$P_{5}$ which is a contradiction. So $u\notin B_{23}\cup B_{24}$. Now by
Observation 3.3(a), $u\in A_{2}\cup B_{12}\cup T_{2}\cup T_{3}\cup T_{4}$.
Since $u$ is an arbitrary vertex of $N(X)\cap N(P)$, we have $N(X)\cap
N(P)\subseteq A_{2}\cup B_{12}\cup T_{2}\cup T_{3}\cup T_{4}$. ∎

######  Claim 2.

If $x\in X$ and $N(x)\cap T_{2}=\emptyset$, then the robber gets captured.

###### Proof of Claim 2.

Suppose that $x\in X$ and $N(x)\cap T_{2}=\emptyset$. By Observation 3.3(c),
$x$ is at distance $2$ from $P$ and hence $x$ has a neighbor in $N(P)$, say
$y$. Since $N(x)\cap T_{2}=\emptyset$, we have $y\notin T_{2}$; thus $y$ is
adjacent to $v_{2}$ by Claim 1. Moreover, since $y$ is arbitrary, any neighbor
of $x$ in $N(P)$ is a neighbor $v_{2}$. In the next turn, Cop $1$ moves to
$v_{2}$ and Cop $2$ moves to $y$. So if the robber moves to a vertex of
$N(P)$, then it gets captured by Cop $1$. Hence the robber should stay in $X$.
Now by Observation 3.3(b), $y$ is adjacent to every vertex of $N[x]\cap X$. So
the robber gets captured by Cop $2$. ∎

######  Claim 3.

If $x\in X$, $N(x)\cap T_{2}\neq\emptyset$, and every vertex of $N(x)\cap
T_{2}$ has a non-neighbor in $N(x)\cap A_{2}$, then the robber gets captured.

###### Proof of Claim 3.

Suppose that $x\in X$, $N(x)\cap T_{2}\neq\emptyset$, and every vertex of
$N(x)\cap T_{2}$ has a non-neighbor in $N(x)\cap A_{2}$. Recall that $a_{1}\in
A_{1}$. Since $x\in X$, by Claim 1, $a_{1}$ is not adjacent to $x$. In the
next turn, Cop $1$ and Cop $2$ move to $a_{1}$ and $v_{1}$, respectively. The
robber can stay in $X$ or move to a vertex $y\in N(x)\cap N(P)$ that is not
adjacent to $a_{1}$ and $v_{1}$ if exists. Suppose that such a vertex $y$
exists. Since $y\in N(X)\cap N(P)$ and $y$ is not adjacent to $v_{1}$, by
Claim 1, $y\in A_{2}$. Now since $a_{1}$ is not adjacent to $y$,
$\\{a_{1},v_{1},v_{2},y,x\\}$ induces a $P_{5}$, a contradiction. So such a
vertex $y$ does not exist and hence the robber should stay in $X$. By
Observation 3.3(b), without loss of generality, we may assume that it stays at
$x$. In the next turn, Cop $1$ stays at $a_{1}$ and Cop $2$ moves to a vertex
$c\in N(x)\cap T_{2}$. Such a vertex $c$ exists since $N(x)\cap
T_{2}\neq\emptyset$. To avoid immediate capture, the robber should move to a
vertex $r\in X\cup N(P)$ that is not adjacent to $a_{1}$ and $c$. By
Observation 3.3(b), $c$ is adjacent to every vertex of $N[x]\cap X$. So
$r\notin X$ and hence $r\in N(P)$. Since $r$ is adjacent to $x$, $r\in
N(X)\cap N(P)$. Then by Claim 1, $r\in A_{2}\cup B_{12}\cup T_{2}\cup
T_{3}\cup T_{4}$. Now we show that $a_{1}$ is adjacent to every vertex of
$N(x)\cap T_{2}$. For the sake of contradiction, suppose that $w\in N(x)\cap
T_{2}$ is not adjacent to $a_{1}$. By our assumption in the claim, $w$ has a
non-neighbor in $N(x)\cap A_{2}$, say $a_{2}$. Recall that $a_{1}$ is not
adjacent to $x$. Then either $\\{a_{1},a_{2},x,w,v_{3}\\}$ or
$\\{a_{1},v_{1},v_{2},a_{2},x\\}$ induces a $P_{5}$, a contradiction. So
$a_{1}$ is adjacent to every vertex of $N(x)\cap T_{2}$. In particular,
$a_{1}$ is adjacent to $c$. Now since $a_{1}$ is adjacent to every vertex of
$N(x)\cap T_{2}$ and not adjacent to $r$, we have $r\notin T_{2}$. So $r\in
A_{2}\cup B_{12}\cup T_{3}\cup T_{4}$. Then $\\{v_{2},r,x,c,a_{1}\\}$ induces
a $P_{5}$, a contradiction. So such a vertex $r$ does not exist. Hence the
robber cannot escape from $x$ and gets captured by Cop $2$. ∎

######  Claim 4.

If $x\in X$ and there exists a vertex in $N(x)\cap T_{2}$ that is adjacent to
every vertex of $N(x)\cap A_{2}$, then the robber gets captured.

###### Proof of Claim 4.

Let $x\in X$ and $c$ be a vertex of $N(x)\cap T_{2}$ that is adjacent to every
vertex of $N(x)\cap A_{2}$. In the next turn, Cop $1$ moves to $c$ and Cop $2$
moves to $v_{1}$. To avoid immediate capture, the robber should move to a
vertex $r$ that is not adjacent to $c$ and $v_{1}$. By Observation 3.3(b), $c$
is adjacent to every vertex of $N[x]\cap X$. So $r\notin X$ and hence $r\in
N(x)\cap N(P)$. Since $x\in X$, we have $r\in N(X)\cap N(P)$. Now by Claim 1,
$r\in A_{2}\cup B_{12}\cup T_{2}\cup T_{3}\cup T_{4}$. Again since $r$ is not
adjacent to $v_{1}$, we have $r\in A_{2}$. This is a contradiction since $c$
is adjacent to every vertex of $N(x)\cap A_{2}$. So such a vertex $r$ does not
exist. Hence the robber cannot escape from $x$ and gets captured by Cop $1$. ∎

######  Claim 5.

If $x\in B_{34}$ and $B_{13}\neq\emptyset$ or $B_{14}\neq\emptyset$, then the
robber gets captured.

###### Proof of Claim 5.

Suppose that $x\in B_{34}$ and $B_{13}\neq\emptyset$. Let $b$ be any vertex of
$B_{13}$. Since $\\{b,v_{1},v_{2},v_{4},x\\}$ does not induce a $P_{5}$, $b$
is adjacent to $x$. Again, $b$ is adjacent to $a_{1}$; otherwise
$\\{v_{4},v_{3},b,v_{1},a_{1}\\}$ induces a $P_{5}$. First we show that
$B_{14}=\emptyset$. For the sake of contradiction, let $b^{\prime}$ be any
vertex of $B_{14}$. Note that $b^{\prime}$ is a neighbor of $a_{1}$; otherwise
$\\{v_{3},v_{4},b^{\prime},v_{1},a_{1}\\}$ induces a $P_{5}$. If $b$ is not
adjacent to $b^{\prime}$, then $\\{b,a_{1},b^{\prime},v_{4},v_{2}\\}$ induces
a $P_{5}$, a contradiction. So $b$ is adjacent to $b^{\prime}$. Again since
$\\{a_{1},v_{1},v_{2},v_{3},x\\}$ does not induce a $P_{5}$, $a_{1}$ is
adjacent to $x$. Then either $\\{a_{1},b,b^{\prime},x\\}$ induces a $K_{4}$ or
$\\{b^{\prime},v_{1},v_{2},v_{3},x\\}$ induces a $P_{5}$ which is a
contradiction. Thus $B_{14}=\emptyset$.

In the next turn, Cop $1$ and Cop $2$ moves to $b$ and $v_{1}$, respectively.
Recall that $b$ is adjacent to $x$. To avoid immediate capture, the robber
must move to a vertex $r$ that is not adjacent to $v_{1}$ and $b$. By
Observation 3.2, $r\notin T_{1}$. Since $x\in B_{34}$ and $r$ is a neighbor of
$x$, by Claim 1, $r\notin X$. Recall that $A_{3}=\emptyset$ and
$A_{4}=\emptyset$ and hence $r\notin A_{3}\cup A_{4}$. Again since $r$ is not
adjacent to $v_{1}$ and $b$, we have $r\in\\{v_{4}\\}\cup A_{2}\cup B_{23}\cup
B_{24}\cup B_{34}$. Since neither $\\{r,v_{4},v_{3},x\\}$ induces a $K_{4}$
nor $\\{v_{1},b,v_{3},v_{4},r\\}$ induces a $P_{5}$, we have $r\notin
B_{34}\cup B_{24}$. Recall that $b$ is adjacent to $a_{1}$. If $r\in A_{2}$,
then $\\{a_{1},b,v_{3},v_{2},r\\}$ or $\\{b,a_{1},r,v_{2},v_{4}\\}$ induces a
$P_{5}$, a contradiction. So $r\notin A_{2}$ and hence $r\in\\{v_{4}\\}\cup
B_{23}$. In the next turn, Cop $1$ moves to $v_{3}$ and Cop $2$ moves to
$v_{2}$. If $r=v_{4}$, then, since $A_{4}=B_{14}=\emptyset$, we have
$N[r]\subseteq N[v_{2}]\cup N[v_{3}]$ implying that the robber gets captured.
So we may assume that $r\in B_{23}$. Note that $r$ does not have any neighbor
in $A_{1}$; otherwise for any neighbor $a\in A_{1}$ of $r$,
$\\{v_{1},a,r,v_{3},v_{4}\\}$ induces a $P_{5}$. Since
$A_{4}=B_{14}=\emptyset$, to avoid immediate capture, the robber should move
to a vertex $r^{\prime}\in X$. Since $b\in B_{13}$, by Claim 1, $r^{\prime}$
is not adjacent to $b$. Then $\\{r^{\prime},r,v_{2},v_{1},b\\}$ induces a
$P_{5}$ which is a contradiction. So such a vertex $r^{\prime}$ does not
exist. Hence the robber cannot escape from $r$ and gets captured. Similarly,
we can show that the robber gets captured if $B_{14}\neq\emptyset$ (due to
symmetry). ∎

######  Claim 6.

If $x\in B_{34}$, $B_{13}=B_{14}=\emptyset$, and every vertex in $N(x)\cap
A_{2}$ has a non-neighbor in $A_{1}$, then the robber gets captured.

###### Proof of Claim 6.

Suppose that $x\in B_{34}$, $B_{13}=B_{14}=\emptyset$, and every vertex in
$N(x)\cap A_{2}$ has a non-neighbor in $A_{1}$. In the next turn, Cop $1$
stays at $v_{1}$ and Cop $2$ moves to $v_{3}$. To avoid immediate capture, the
robber must move to a vertex $r$ that is not adjacent to $v_{1}$ and $v_{3}$.
Since $x\in B_{34}$, by Claim 1, $r\notin X$. Again since $r$ is not adjacent
to $v_{1}$ and $v_{3}$, we have $r\in A_{2}\cup A_{4}\cup B_{24}$. Recall that
$A_{3}=A_{4}=\emptyset$. So $r\notin A_{4}$ and hence $r\in A_{2}\cup B_{24}$.

First assume that $r\in B_{24}$. In the next turn, Cop $1$ moves to $v_{2}$
and Cop $2$ stays at $v_{3}$. To avoid immediate capture, the robber must move
to a vertex $r^{\prime}$ that is not adjacent to $v_{2}$ and $v_{3}$. Since
$A_{4}=B_{14}=\emptyset$, we have $r^{\prime}\in A_{1}\cup X$. Again since
$\\{v_{3},v_{4},r,r^{\prime},v_{1}\\}$ does not induce a $P_{5}$,
$r^{\prime}\notin A_{1}$. So $r^{\prime}\in X$. By Claim 1, $a_{1}$ is not
adjacent to $r^{\prime}$. Note that $a_{1}$ is not adjacent to $r$; otherwise
$\\{v_{3},v_{4},r,a_{1},v_{1}\\}$ induces a $P_{5}$. Then
$\\{a_{1},v_{1},v_{2},r,r^{\prime}\\}$ induces a $P_{5}$ which is a
contradiction. So such a vertex $r^{\prime}$ does not exist. Hence the robber
cannot escape from $r$ and gets captured by Cop $1$.

Now suppose that $r\in A_{2}$. Since $r\in N(x)\cap A_{2}$, due to our
assumption in the claim, $r$ has a non-neighbor in $A_{1}$, say $a^{\prime}$.
Recall that Cop $1$, Cop $2$, and the robber are at $v_{1},v_{3},$ and $r$,
respectively. In the next turn, Cop $1$ moves to $v_{2}$ and Cop $2$ stays at
$v_{3}$. To avoid immediate capture, the robber must move to a vertex
$r^{\prime}$ that is not adjacent to $v_{2}$ and $v_{3}$. Since
$A_{4}=B_{14}=\emptyset$, we have $r^{\prime}\in A_{1}\cup X$. Suppose that
$r^{\prime}\in X$. Note that by Claim 1, $a^{\prime}$ is not adjacent to
$r^{\prime}$. Then $\\{a^{\prime},v_{1},v_{2},r,r^{\prime}\\}$ induces a
$P_{5}$ which is a contradiction. So we may assume that $r^{\prime}\in A_{1}$.
In the next turn, Cop $1$ and Cop $2$ move to $r$ and $v_{2}$, respectively.
To avoid immediate capture, robber must move to a vertex $r^{\prime\prime}$
that is not adjacent to $r$ and $v_{2}$. Since $r^{\prime}\in A_{1}$, by Claim
1, $r^{\prime\prime}\notin X$. Again since
$A_{3}=A_{4}=B_{13}=B_{14}=\emptyset$ and $r^{\prime\prime}$ is not adjacent
to $v_{2}$, we have $r^{\prime\prime}\in A_{1}\cup B_{34}\cup T_{2}$. Note
that $r^{\prime\prime}\notin A_{1}$; otherwise
$\\{r^{\prime\prime},r^{\prime},r,v_{2},v_{3}\\}$ induces a $P_{5}$. Recall
that $a^{\prime}\in A_{1}$ is a non-neighbor of $r$. Since neither
$\\{a^{\prime},v_{1},v_{2},v_{3},r^{\prime\prime}\\}$ nor
$\\{r,v_{2},v_{1},a^{\prime},r^{\prime\prime}\\}$ induces a $P_{5}$, we have
$r^{\prime\prime}\notin B_{34}$. So $r^{\prime\prime}\in T_{2}$. Then either
$\\{r^{\prime\prime},x,v_{3},v_{4}\\}$ induces a $K_{4}$ or
$\\{r,x,v_{3},r^{\prime\prime},v_{1}\\}$ induces a $P_{5}$ which is a
contradiction. So such a vertex $r^{\prime\prime}$ does not exist. Hence the
robber cannot escape from $r^{\prime}$ and gets captured by Cop $1$. ∎

We now return to the proof of Lemma 3.4. Recall that Cop $1$, Cop $2$, and the
robber are at $v_{1}$, $v_{2}$, and $x\in B_{34}\cup X$, respectively. First
assume that $x\in X$. If $N(x)\cap T_{2}=\emptyset$, then by Claim 2, the
robber gets captured. So we may assume that $N(x)\cap T_{2}\neq\emptyset$. If
every vertex of $N(x)\cap T_{2}$ has a non-neighbor in $N(x)\cap A_{2}$, then
by Claim 3, the robber gets captured. So we may assume that there exists a
vertex in $N(x)\cap T_{2}$ that is adjacent to every vertex of $N(x)\cap
A_{2}$. Then by Claim 4, the robber gets captured.

Now assume that $x\in B_{34}$. If $B_{13}\neq\emptyset$ or
$B_{14}\neq\emptyset$, then by Claim 5, the robber gets captured. So assume
that $B_{13}=B_{14}=\emptyset$. Now if every vertex of $N(x)\cap A_{2}$ has a
non-neighbor in $A_{1}$, then by Claim 6, the robber gets captured. Note that
Claim 6 also includes the case $N(x)\cap A_{2}=\emptyset$. So we may assume
that there exists a vertex $a_{2}\in N(x)\cap A_{2}$ such that $a_{2}$ is
adjacent to every vertex of $A_{1}$. Recall that the cops are at $v_{1}$ and
$v_{2}$ whereas the robber is at $x\in B_{34}$. In the next turn, Cop $1$ and
Cop $2$ move to $v_{2}$ and $a_{2}$, respectively. Now if the robber does not
move, then, since $a_{2}$ is adjacent to $x$, it gets captured by Cop $2$. To
avoid immediate capture, it must move to a vertex $r$ that is not adjacent to
$v_{2}$ and $a_{2}$. Since $x\in B_{34}$, by Claim 1, $x$ does not have any
neighbor in $X$ implying that $r\notin X$. Recall that
$A_{3}=A_{4}=B_{13}=B_{14}=\emptyset$ and $a_{2}$ is adjacent to every vertex
of $A_{1}$. So $r\in B_{34}\cup T_{2}$. Then $\\{x,r,v_{3},v_{4}\\}$ induces a
$K_{4}$ which is a contradiction. So such a vertex $r$ does not exist. Hence
the robber cannot escape from $x$ and gets captured implying that $cop(G)\leq
2$. This completes the proof of Lemma 3.4. ∎

In the following lemma, we show that the cop number of any connected
($P_{5},K_{4}$, co-banner)-free graph that has an induced butterfly is at most
$2$. The idea of the proof is similar to the proof of Lemma 3.4.

######  Lemma 3.5.

Let $G$ be a connected $(P_{5},K_{4}$, co-banner$)$-free graph that has an
induced butterfly. Then $cop(G)\leq 2$.

###### Proof.

Let $\\{b,v_{1},v_{2},v_{3},v_{4}\\}$ induce a butterfly in $G$ with edge set
$\\{bv_{1},v_{1}v_{2},bv_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{2}\\}$. Note that
$P=\\{v_{1},v_{2},v_{3},v_{4}\\}$ induces a paw in $G$. Define the sets
$A_{i},B_{ij},T_{i},D$, and $X$ around $P$ for every $1\leq i,j\leq 4$ and
$i<j$ as defined in • ‣ 2. Note that $b\in B_{12}$. Again note that
$A_{1}=\emptyset$; otherwise $G[P\cup A_{1}]$ contains an induced co-banner.
If $B_{14}\neq\emptyset$, then for any $b^{\prime}\in B_{14}$,
$\\{b,v_{1},b^{\prime},v_{4},v_{3}\\}$ induces a $P_{5}$ or a co-banner, a
contradiction. So $B_{14}=\emptyset$. In the first turn, we place Cop $1$ and
Cop $2$ at $v_{3}$ and $v_{4}$, respectively. To avoid immediate capture, the
robber must choose a vertex $r$ that is not adjacent to $v_{3}$ and $v_{4}$.
Since $A_{1}=\emptyset$, we have $r\in\\{v_{1}\\}\cup A_{2}\cup B_{12}\cup X$.

######  Claim 7.

If a vertex $w$ has a neighbor in $\\{v_{1}\\}\cup A_{2}\cup B_{12}$, then $w$
is adjacent to $v_{2}$ or $v_{3}$.

###### Proof of Claim 7.

Let $w$ be a vertex that is not adjacent to $v_{2}$ and $v_{3}$. Note that $w$
is not a vertex of the butterfly induced by $\\{b,v_{1},v_{2},v_{3},v_{4}\\}$.
To prove the claim, it is sufficient to show that $w$ does not have any
neighbor in $\\{v_{1}\\}\cup A_{2}\cup B_{12}$. For the sake of contradiction,
suppose that $w$ has a neighbor $u$ in $\\{v_{1}\\}\cup A_{2}\cup B_{12}$.
Note that $w$ is adjacent to $v_{4}$; otherwise $\\{w,u,v_{2},v_{3},v_{4}\\}$
induces a co-banner. If $w$ is adjacent to $v_{1}$, then $w\in B_{14}$, a
contradiction to the fact that $B_{14}=\emptyset$. So $w$ is not adjacent to
$v_{1}$. Recall that $b\in B_{12}$. Note that $w$ is not adjacent to $b$;
otherwise $\\{v_{1},b,w,v_{4},v_{3}\\}$ induces a $P_{5}$. Now
$\\{v_{1},b,v_{2},v_{4},w\\}$ induces a co-banner, a contradiction. Therefore,
$w$ does not have any neighbor in $\\{v_{1}\\}\cup A_{2}\cup B_{12}$. ∎

######  Claim 8.

$N(P)\cap N(X)\subseteq N(b)\cap(B_{23}\cup B_{24}\cup T_{2})$.

###### Proof of Claim 8.

Let $x$ be an arbitrary vertex of $X$. By Observation 3.3(c), $x$ is at
distance $2$ from $P$ and hence $N(x)\cap N(P)\neq\emptyset$. Let $u\in
N(x)\cap N(P)$. Since $\\{v_{3},v_{4},v_{2},u,x\\}$ does not induce a co-
banner, $u\notin A_{2}\cup B_{12}$. Again since neither
$\\{b,u,v_{1},v_{2}\\}$ induces a $K_{4}$ nor $\\{v_{4},v_{3},u,v_{1},b\\}$
induces a $P_{5}$, we have $u\notin T_{3}\cup T_{4}$. Hence by Observation
3.3(a), $u\in B_{23}\cup B_{24}\cup T_{2}$ implying that $N(x)\cap
N(P)\subseteq B_{23}\cup B_{24}\cup T_{2}$. In particular, $b$ is not adjacent
to $x$. Since $\\{b,v_{1},v_{2},u,x\\}$ does not induce a co-banner, $b$ is a
neighbor of $u$. So we have $N(x)\cap N(P)\subseteq N(b)$ and hence $N(x)\cap
N(P)\subseteq N(b)\cap(B_{23}\cup B_{24}\cup T_{2})$. Since $x$ is an
arbitrary vertex of $X$, we have $N(P)\cap N(X)\subseteq N(b)\cap(B_{23}\cup
B_{24}\cup T_{2})$. ∎

We now return to the proof of Lemma 3.5. First suppose that
$r\in\\{v_{1}\\}\cup A_{2}\cup B_{12}$. In the next turn, Cop $1$ stays at
$v_{3}$ and Cop $2$ moves to $v_{2}$. Now by Claim 7, every vertex of $N[r]$
is adjacent to $v_{2}$ or $v_{3}$. So wherever the robber moves, it gets
captured. Hence we may assume that $r\in X$. By Observation 3.3(c) and Claim
8, there exists a vertex $u\in N(P)$ that is a common neighbor of $r$ and
$v_{i}$ for some $i\in\\{3,4\\}$. In the next turn, Cop $1$ moves to $v_{2}$
and Cop $2$ chooses $v_{i}$ as its position. By Claim 8, every vertex of
$N(P)\cap N(r)$ is adjacent to $v_{2}$ or $v_{i}$. So if the robber moves to
$N(P)$, then it gets captured and hence the robber should stay in $X$. By
Observation 3.3(b), without loss of generality, we may assume that the robber
stays at $r$. In the next turn, Cop $1$ and Cop $2$ move to $b$ and $u$,
respectively. To avoid immediate capture, the robber must move to a vertex of
$X\cup N(P)$. By Observation 3.3(b), $u$ is adjacent to every vertex of
$N[r]\cap X$. So if the robber stays in $X$, then it gets captured by Cop $2$.
Hence the robber must move to a vertex of $N(P)$. Now by Claim 8, $b$ is
adjacent to every vertex of $N(X)\cap N(P)$. So the robber gets captured by
the cop at $b$. Therefore, $cop(G)\leq 2$. This completes the proof of Lemma
3.5. ∎

In the following lemma, we prove that the robber gets captured in a connected
$(P_{5},K_{4},$ co-banner, butterfly$)$-free graph if at the end of a round,
the two cops and the robber are at some specific vertices of the graph.

######  Lemma 3.6.

Suppose that $G$ is a connected $(P_{5},K_{4}$, co-banner, butterfly$)$-free
graph and $P$ induces a paw in $G$. If at the end of a round in the game of
cops and robber, two cops are at two distinct degree $2$ vertices of the graph
$G[P]$ and the robber is at a vertex at distance $2$ from $P$, then the robber
gets captured.

###### Proof.

Let $P=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and the edge set of the paw induced by
$P$ be $\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{2}\\}$. Define the sets
$A_{i},B_{ij},T_{i},D$, and $X$ around $P$ as defined in • ‣ 2 for every
$1\leq i,j\leq 4$ and $i<j$. We may assume that Cop $1$ is at $v_{3}$, Cop $2$
is at $v_{4}$, and the robber is at $r\in X$ at the end of a round in the game
of cops and robber. Note that it is now cops’ turn to move. Again note that
$A_{1}=B_{12}=\emptyset$; otherwise $G[P\cup A_{1}]$ or $G[P\cup B_{12}]$
contains an induced co-banner or butterfly. To proceed further, we prove a
series of claims.

######  Claim 9.

$N(X)\cap N(P)\subseteq B_{23}\cup B_{24}\cup T_{2}\cup T_{3}\cup T_{4}$.

###### Proof of Claim 9.

Let $y$ be an arbitrary vertex of $N(X)\cap N(P)$ and $x$ be a neighbor of $y$
in $X$. Since $B_{12}=\emptyset$, by Observation 3.3(a), $y\in A_{2}\cup
B_{23}\cup B_{24}\cup T_{2}\cup T_{3}\cup T_{4}$. Again since
$\\{v_{3},v_{4},v_{2},y,x\\}$ does not induce a co-banner, we have $y\notin
A_{2}$. So $y\in B_{23}\cup B_{24}\cup T_{2}\cup T_{3}\cup T_{4}$. ∎

######  Claim 10.

If $N(r)\cap B_{23}\neq\emptyset$, $T_{3}\neq\emptyset$, and
$T_{4}\neq\emptyset$, then the robber gets captured.

###### Proof of Claim 10.

Let $b\in N(r)\cap B_{23}$, $c\in T_{3}$, and $c^{\prime}\in T_{4}$. In the
next turn, Cop $1$ and Cop $2$ move to $b$ and $v_{3}$, respectively. Since
$b$ is adjacent to $r\in X$, by Observation 3.3(b), $b$ is adjacent to every
vertex of $N[r]\cap X$. So if the robber stays in $X$, then it gets captured
by Cop $1$. So to avoid immediate capture, the robber must move to a vertex
$r^{\prime}\in N(r)\cap N(P)$ that is not adjacent to $b$ and $v_{3}$. Since
$r^{\prime}\in N(X)\cap N(P)$ and $r^{\prime}$ is not adjacent to $v_{3}$, by
Claim 9, $r^{\prime}\in B_{24}\cup T_{3}$. Suppose that $r^{\prime}\in
B_{24}$. Since $\\{b,v_{3},v_{2},c^{\prime}\\}$ does not induce a $K_{4}$, $b$
is not adjacent to $c^{\prime}$. Again since $\\{r^{\prime},v_{4},v_{2},c\\}$
and $\\{c,v_{1},v_{2},c^{\prime}\\}$ do not induce any $K_{4}$, $c$ is not
adjacent to $r^{\prime}$ and $c^{\prime}$. Note that $r^{\prime}$ is adjacent
to $c^{\prime}$; otherwise $\\{r^{\prime},v_{4},v_{3},c^{\prime},v_{1}\\}$
induces a $P_{5}$. Similarly, $b$ is adjacent to $c$; otherwise
$\\{b,v_{3},v_{4},c,v_{1}\\}$ induces a $P_{5}$. Then
$\\{b,c,v_{1},c^{\prime},r^{\prime}\\}$ induces a $P_{5}$ which is a
contradiction to our assumption that $r^{\prime}\in B_{24}$. So we have
$r^{\prime}\in T_{3}$. Now since $r^{\prime}$ is not adjacent to $b$,
$\\{b,v_{3},v_{4},r^{\prime},v_{1}\\}$ induces a $P_{5}$, a contradiction. So
such a vertex $r^{\prime}$ does not exist. Hence the robber cannot escape from
$r$ and gets captured. ∎

######  Claim 11.

If $T_{4}=\emptyset$ and $N(r)\cap T_{3}\neq\emptyset$, then the robber gets
captured.

###### Proof of Claim 11.

Let $T_{4}=\emptyset$ and $c\in N(r)\cap T_{3}$. In the next turn, Cop $1$ and
Cop $2$ move to $v_{4}$ and $c$, respectively. Since $r\in X$ and $c$ is
adjacent to $r$, by Observation 3.3(b), $c$ is adjacent to every vertex of
$N[r]\cap X$. So if the robber stays in $X$, then it gets captured. So we may
assume that the robber moves to a vertex $r^{\prime}\in N(r)\cap N(P)$ that is
not adjacent to $v_{4}$ and $c$. Now since $T_{4}=\emptyset$ and $r^{\prime}$
is not adjacent to $v_{4}$, by Claim 9, $r^{\prime}\in B_{23}$. Then
$\\{v_{1},c,v_{4},v_{3},r^{\prime}\\}$ induces a $P_{5}$, a contradiction. So
such a vertex $r^{\prime}$ does not exist. Hence the robber cannot escape from
$r$ and gets captured. ∎

######  Claim 12.

If $N(r)\cap(T_{3}\cup T_{4})=\emptyset$, $N(r)\cap B_{23}\neq\emptyset$,
$N(r)\cap B_{24}\neq\emptyset$, and $B_{13}\neq\emptyset$ or
$B_{14}\neq\emptyset$, then the robber gets captured.

###### Proof of Claim 12.

Let $N(r)\cap(T_{3}\cup T_{4})=\emptyset$ and $b\in N(r)\cap B_{23}$. First
assume that $B_{13}\neq\emptyset$. Let $b_{1}\in B_{13}$. In the next turn,
Cop $1$ stays at $v_{3}$ and Cop $2$ moves to $v_{2}$. Note that by Claim 9,
every vertex in $N(r)\cap N(P)$ is adjacent to $v_{2}$ or $v_{3}$. So if the
robber moves to a vertex of $N(P)$, then it gets captured. Hence the robber
should stay in $X$. By Observation 3.3(b), without loss of generality, we may
assume that the robber stays at $r$. In the next turn, Cop $1$ and Cop $2$
move to $b$ and $b_{1}$, respectively. Since $b$ is adjacent to $r\in X$, by
Observation 3.3(b), $b$ is adjacent to every vertex of $N[r]\cap X$. So if the
robber stays in $X$, then its gets captured by Cop $1$. To avoid immediate
capture, robber must move to a vertex $r^{\prime}\in N(r)\cap N(P)$ that is
not adjacent to $b$ and $b_{1}$. Since $r^{\prime}\in N(X)\cap N(P)$, by Claim
9, $r^{\prime}\in B_{23}\cup B_{24}\cup T_{2}\cup T_{3}\cup T_{4}$. Since
$b_{1}\in B_{13}$ and $r\in X$, by Claim 9, $b_{1}$ is not adjacent to $r$.
Now since $\\{b_{1},v_{1},v_{2},r^{\prime},r\\}$ does not induce a $P_{5}$, we
have $r^{\prime}\notin B_{23}\cup B_{24}$. So $r^{\prime}\in T_{2}\cup
T_{3}\cup T_{4}$. Again since $N(r)\cap(T_{3}\cup T_{4})=\emptyset$, we have
$r^{\prime}\in T_{2}$. Note that $b$ is adjacent to $b_{1}$; otherwise
$\\{b_{1},v_{1},v_{2},b,r\\}$ induces a $P_{5}$. Then
$\\{b_{1},b,r,r^{\prime},v_{4}\\}$ induces a $P_{5}$ which is a contradiction.
So such a vertex $r^{\prime}$ does not exist. Hence the robber cannot escape
from $r$ and gets captured. Now if $B_{14}\neq\emptyset$, then, since
$N(r)\cap B_{24}\neq\emptyset$, we may conclude that the robber gets captured
(due to symmetry). ∎

######  Claim 13.

If $T_{4}=N(r)\cap T_{3}=B_{14}=\emptyset$ and $N(r)\cap B_{23}\neq\emptyset$,
then the robber gets captured.

###### Proof of Claim 13.

Let $T_{4}=N(r)\cap T_{3}=B_{14}=\emptyset$ and $b\in N(r)\cap B_{23}$. First
assume that $r$ has no neighbor in $T_{2}$. In the next turn, Cop $1$ and Cop
$2$ move to $b$ and $v_{2}$, respectively. Since $b$ is adjacent to $r\in X$,
by Observation 3.3(b), $b$ is adjacent to every vertex of $N[r]\cap X$. So if
the robber stays in $X$, then it gets captured by Cop $1$. So the robber must
move to a vertex of $N(r)\cap N(P)$. Now since $r\in X$ and $r$ has no
neighbor in $T_{2}$, by Claim 9, the robber must move to a vertex of
$B_{23}\cup B_{24}\cup T_{3}\cup T_{4}$. Then the cop at $v_{2}$ captures the
robber.

So we may assume that $r$ has a neighbor in $T_{2}$, say $c_{1}$. In the next
turn, Cop $1$ moves to $c_{1}$ and Cop $2$ stays at $v_{4}$. Since $c_{1}$ is
adjacent to $r\in X$, by Observation 3.3(b), $c_{1}$ is adjacent to every
vertex of $N[r]\cap X$. So if the robber stays in $X$, then it gets captured
by Cop $1$. So to avoid immediate capture, the robber must move to vertex
$r^{\prime}\in N(r)\cap N(P)$ that is not adjacent to $c_{1}$ and $v_{4}$.
Since $T_{4}=\emptyset$ and $r^{\prime}$ is not adjacent to $v_{4}$, by Claim
9, we have $r^{\prime}\in B_{23}$. In the next turn, Cop $1$ stays at $c_{1}$
and Cop $2$ moves to $v_{3}$. Again to avoid immediate capture, the robber
must move to a vertex $r^{\prime\prime}$ that is not adjacent to $v_{3}$ and
$c_{1}$. Since $A_{1}=B_{12}=B_{14}=\emptyset$ and $r^{\prime\prime}$ is not
adjacent to $v_{3}$, we have $r^{\prime\prime}\in A_{2}\cup A_{4}\cup
B_{24}\cup T_{3}\cup X$. If $r^{\prime\prime}\in X$, then
$\\{r^{\prime\prime},r^{\prime},v_{2},v_{4},c_{1}\\}$ induces a $P_{5}$, a
contradiction. Thus $r^{\prime\prime}\notin X$. Since
$\\{r^{\prime\prime},v_{2},r^{\prime},v_{1},c_{1}\\}$ does not induce a co-
banner, we have $r^{\prime\prime}\notin A_{2}\cup B_{24}$. If
$r^{\prime\prime}\in T_{3}$, then by our assumption in the claim that
$N(r)\cap T_{3}=\emptyset$, we conclude that $r$ is not adjacent to
$r^{\prime\prime}$. Now $\\{r^{\prime\prime},v_{2},v_{4},c_{1},r\\}$ induces a
co-banner, a contradiction. So $r^{\prime\prime}\notin T_{3}$. Hence
$r^{\prime\prime}\in A_{4}$. Since $r\in X$ and $r^{\prime\prime}\in A_{4}$,
by Claim 9, $r^{\prime\prime}$ is not adjacent to $r$. Then
$\\{r^{\prime\prime},r^{\prime},r,c_{1},v_{1}\\}$ induces a $P_{5}$ which is a
contradiction. So such a vertex $r^{\prime\prime}$ does not exist. Hence the
robber cannot escape from $r^{\prime}$ and gets captured. ∎

######  Claim 14.

If $N(r)\cap B_{23}=N(r)\cap B_{24}=\emptyset$, then the robber gets captured.

###### Proof of Claim 14.

Suppose that $N(r)\cap B_{23}=N(r)\cap B_{24}=\emptyset$. So by Claim 9,
$N(r)\cap N(P)\subseteq T_{2}\cup T_{3}\cup T_{4}$. In the next turn, Cop $1$
moves to $v_{2}$ and Cop $2$ stays at $v_{4}$. Note that every vertex of
$N(r)\cap N(P)$ is adjacent to $v_{2}$ or $v_{4}$. So to avoid capture, the
robber should stay in $X$. By Observation 3.3(b), without loss of generality,
we may assume that the robber stays at $r$. In the next turn, Cop $1$ and Cop
$2$ move to $v_{1}$ and $v_{2}$, respectively. Since $N(r)\cap N(P)\subseteq
T_{2}\cup T_{3}\cup T_{4}$, every vertex of $N(r)\cap N(P)$ is adjacent to
$v_{1}$. So if the robber moves to a vertex of $N(P)$, then it gets captured
by Cop $1$ and hence the robber should stay in $X$. By Observation 3.3(b),
without loss of generality, we may assume that the robber stays at $r$. Since
$r$ is at distance $2$ from $P$, $N(r)\cap N(P)\neq\emptyset$. Let $x\in
N(r)\cap N(P)$. In the next turn, Cop $1$ and Cop $2$ move to $x$ and $v_{1}$,
respectively. Since $x\in N(X)\cap N(P)$, by Observation 3.3(b), $x$ is
adjacent to every vertex of $N[r]\cap X$. So if the robber stays in $X$, then
Cop $1$ captures it and hence the robber should move to a vertex of $N(r)\cap
N(P)$. Then the robber gets captured by the cop at $v_{1}$ since every vertex
of $N(r)\cap N(P)$ is adjacent to $v_{1}$. ∎

We now return to the proof of Lemma 3.6. First assume that $N(r)\cap
B_{23}\neq\emptyset$ and $N(r)\cap B_{24}\neq\emptyset$. If
$T_{3}\neq\emptyset$ and $T_{4}\neq\emptyset$, then by Claim 10, the robber
gets captured. So we may assume that $T_{3}=\emptyset$ or $T_{4}=\emptyset$.
Due to symmetry, we may assume that $T_{4}=\emptyset$. Now if $N(r)\cap
T_{3}\neq\emptyset$, then by Claim 11, the robber gets captured. So we may
further assume that $N(r)\cap T_{3}=\emptyset$. Now if $B_{13}\neq\emptyset$
or $B_{14}\neq\emptyset$, then by Claim 12, the robber gets captured. So we
may assume that $B_{13}=B_{14}=\emptyset$. Now by Claim 13, the robber gets
captured. This implies that the robber gets captured if $N(r)\cap
B_{23}\neq\emptyset$ and $N(r)\cap B_{24}\neq\emptyset$. So we may assume that
$N(r)\cap B_{23}=\emptyset$ or $N(r)\cap B_{24}=\emptyset$. If $N(r)\cap
B_{23}=\emptyset$ and $N(r)\cap B_{24}=\emptyset$, then by Claim 14, the
robber gets captured. So we may assume that exactly one of the sets $N(r)\cap
B_{23}$ and $N(r)\cap B_{24}$ is empty. Due to symmetry, we may further assume
that $N(r)\cap B_{23}=\emptyset$ and $N(r)\cap B_{24}\neq\emptyset$. Let $b\in
N(r)\cap B_{24}$. Recall that Cop $1$, Cop $2$, and the robber are at
$v_{3},v_{4},$ and $r\in X$, respectively. In the next turn, Cop $1$ and Cop
$2$ move to $v_{4}$ and $b$, respectively. Since $b$ is adjacent to $r\in X$,
by Observation 3.3(b), $b$ is adjacent to every vertex in $N[r]\cap X$. So if
the robber stays in $X$, then it gets captured by Cop $2$. To avoid immediate
capture, the robber must move to a vertex $r^{\prime}\in N(r)\cap N(P)$ that
is not adjacent to $b$ and $v_{4}$. Since $N(r)\cap B_{23}=\emptyset$,
$r^{\prime}\notin B_{23}$. Again since $r^{\prime}$ is adjacent to $r\in X$
and is not adjacent to $v_{4}$, by Claim 9, $r^{\prime}\in T_{4}$. Then
$\\{b,v_{4},v_{3},r^{\prime},v_{1}\\}$ induces a $P_{5}$ which is a
contradiction. So such a vertex $r^{\prime}$ does not exist. Hence the robber
cannot escape from $r$ and gets captured. This completes the proof of Lemma
3.6. ∎

In the following lemma, we show that if $G$ is a connected $(P_{5},K_{4}$, co-
banner, butterfly$)$-free graph that has an induced kite and the two cops and
the robber are at some specific vertices of $G$ at the end of a round, then
the robber gets captured.

######  Lemma 3.7.

Suppose that $G$ is a connected $(P_{5},K_{4}$, co-banner, butterfly$)$-free
graph that has an induced kite. Let $P$ induce a paw in $G$ that is contained
in an induced kite of $G$. If at the end of a round in the game of cops and
robber, two cops are at two distinct degree $2$ vertices of the graph $G[P]$
and the robber is at the degree $1$ vertex of $G[P]$, then the robber gets
captured.

###### Proof.

Let $P=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and the edge set of the paw induced by
$P$ be $\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{2}\\}$. We may assume that
Cop $1$, Cop $2$, and the robber are at $v_{3},v_{4}$, and $v_{1}$,
respectively at the end of a round in the game of cops and robber. Note that
it is now cops’ turn to move. Define the sets $A_{i},B_{ij},T_{i},D$, and $X$
around $P$ for every $1\leq i,j\leq 4$ and $i<j$ as defined in • ‣ 2. Since
the paw induced by $P$ is contained in an induced kite of $G$, we have
$B_{34}\neq\emptyset$. Let $b\in B_{34}$. Note that $A_{1}=B_{12}=\emptyset$;
otherwise for any $u\in A_{1}\cup B_{12}$, $P\cup\\{u\\}$ induces a co-banner
or a butterfly in $G$.

######  Claim 15.

If $A_{3}\cup(B_{23}\setminus N(b))\neq\emptyset$ or
$A_{4}\cup(B_{24}\setminus N(b))\neq\emptyset$ or
$[B_{34},A_{2}]\neq\emptyset$, then the robber gets captured.

###### Proof of Claim 15.

Let $a\in A_{3}\cup(B_{23}\setminus N(b))$. First we show that every neighbor
of $v_{1}$ is adjacent to $v_{4}$ or $b$. For the sake of contradiction, let
$x$ be a neighbor of $v_{1}$ such that $x$ is not adjacent to $v_{4}$ and $b$.
Clearly, $x\neq v_{2}$ and hence $x$ is not a vertex of the kite induced by
$\\{v_{1},v_{2},v_{3},v_{4},b\\}$. Then $\\{b,v_{4},v_{2},v_{1},x\\}$ induces
a $P_{5}$ or a co-banner, a contradiction. So every neighbor of $v_{1}$ is
adjacent to $v_{4}$ or $b$. In the next turn, Cop $1$ moves to $b$ and Cop $2$
stays at $v_{4}$. Since every neighbor of $v_{1}$ is adjacent to $v_{4}$ or
$b$, to avoid immediate capture, the robber must stay at $v_{1}$. Now we show
that $a$ and $b$ are not adjacent. If $a\in A_{3}$, then, since
$\\{a,b,v_{4},v_{2},v_{1}\\}$ does not induce a $P_{5}$, $a$ and $b$ are not
adjacent. Again if $a\in B_{23}\setminus N(b)$, then $a$ is not adjacent to
$b$. Note that $P^{\prime}=\\{a,v_{3},b,v_{4}\\}$ induces a paw in $G$. At the
end of this round, the cops are at $b$ and $v_{4}$ that are degree $2$
vertices of $G[P^{\prime}]$ and the robber is at $v_{1}$ that is at distance
$2$ from $P^{\prime}$. So by Lemma 3.6, the robber gets captured. Similarly,
we can show that the robber gets captured if $A_{4}\cup(B_{24}\setminus
N(b))\neq\emptyset$.

Now suppose that $[B_{34},A_{2}]\neq\emptyset$. Let $a\in A_{2}$ and
$b^{\prime}\in B_{34}$ such that $a$ is adjacent to $b^{\prime}$. Note that
$P^{\prime\prime}=\\{a,b^{\prime},v_{3},v_{4}\\}$ induces a paw. Again note
that the cops are at $v_{3}$ and $v_{4}$ that are degree $2$ vertices of
$G[P^{\prime\prime}]$ and the robber is at $v_{1}$ that is at distance $2$
from $P^{\prime\prime}$. So by Lemma 3.6, the robber gets captured. ∎

We now return to the proof of Lemma 3.7. If $A_{3}\cup(B_{23}\setminus
N(b))\neq\emptyset$ or $A_{4}\cup(B_{24}\setminus N(b))\neq\emptyset$, then by
Claim 15, the robber gets captured. So we may assume that
$A_{3}=A_{4}=\emptyset$ and $b$ is adjacent to every vertex of $B_{23}\cup
B_{24}$. If $[B_{34},A_{2}]\neq\emptyset$, then by Claim 15, the robber gets
captured. So we may assume that $[B_{34},A_{2}]=\emptyset$. In the next turn,
Cop $1$ stays at $v_{3}$ and Cop $2$ moves to $v_{2}$. To avoid immediate
capture, the robber must move to a vertex $r^{\prime}$ that is not adjacent to
$v_{3}$ and $v_{2}$. Since $A_{1}=\emptyset$, we have $r^{\prime}\in B_{14}$.
Note that $b$ is adjacent to every vertex of $B_{14}$; otherwise for any non-
neighbor $y\in B_{14}$ of $b$, $\\{b,v_{3},v_{2},v_{1},y\\}$ induces a
$P_{5}$. In particular, $b$ is adjacent to $r^{\prime}$. In the next turn, Cop
$1$ stays at $v_{3}$ and Cop $2$ moves to $v_{1}$. To avoid immediate capture,
the robber must move to a vertex $r^{\prime\prime}$ that is not adjacent to
$v_{3}$ and $v_{1}$. Since $r^{\prime}\in B_{14}$, by Observation 3.3(a),
$r^{\prime\prime}\notin X$. Since $A_{4}=\emptyset$, we have
$r^{\prime\prime}\in A_{2}\cup B_{24}$. If $r^{\prime\prime}\in B_{24}$, then,
since $b$ is adjacent to every vertex of $B_{14}\cup B_{24}$,
$\\{b,v_{4},r^{\prime},r^{\prime\prime}\\}$ induces a $K_{4}$ in $G$ which is
a contradiction. So $r^{\prime\prime}\notin B_{24}$ and hence
$r^{\prime\prime}\in A_{2}$. In the next turn, Cop $1$ moves to $v_{2}$ and
Cop $2$ stays at $v_{1}$. To avoid immediate capture, the robber must move to
a vertex $r_{1}$ that is not adjacent to $v_{1}$ and $v_{2}$. Since
$A_{3}=A_{4}=\emptyset$ and $[B_{34},A_{2}]=\emptyset$, we have $r_{1}\in X$.
Then $\\{v_{3},v_{4},v_{2},r^{\prime\prime},r_{1}\\}$ induces a co-banner
which is a contradiction. So such a vertex $r_{1}$ does not exist. Hence the
robber cannot escape from $r^{\prime\prime}$ and gets captured. This completes
the proof of Lemma 3.7. ∎

We now show that the cop number of any connected $(P_{5},K_{4}$, co-banner,
butterfly$)$-free graph is at most $2$.

######  Lemma 3.8.

Let $G$ be a connected $(P_{5},K_{4}$, co-banner, butterfly$)$-free graph.
Then $cop(G)\leq 2$.

###### Proof.

If $G$ is paw-free, then by Lemma 3.1, $cop(G)\leq 2$. So we may assume that
$G$ contains an induced paw, say with vertex set
$P=\\{v_{1},v_{2},v_{3},v_{4}\\}$ and edge set
$\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{2}v_{4}\\}$. Define sets
$A_{i},B_{ij},T_{i},D,$ and $X$ around $P$ for every $1\leq i,j\leq 4$ and
$i<j$ as defined in • ‣ 2. Since $G$ is $($co-banner, butterfly$)$-free, we
have $A_{1}=B_{12}=\emptyset$. In the first turn, we place Cop $1$ and Cop $2$
at $v_{3}$ and $v_{4}$, respectively. To avoid immediate capture, the robber
must choose a vertex $r$ that is not adjacent to $v_{3}$ and $v_{4}$. Since
$A_{1}=B_{12}=\emptyset$ and $r$ is not adjacent to $v_{3}$ and $v_{4}$, we
have $r\in\\{v_{1}\\}\cup A_{2}\cup X$. If $r\in X$, then by Lemma 3.6, the
robber gets captured. So we may assume that $r\in\\{v_{1}\\}\cup A_{2}$. Due
to symmetry, we may further assume that $r=v_{1}$. Now if
$B_{34}\neq\emptyset$, then by Lemma 3.7, the robber gets captured. So assume
that $B_{34}=\emptyset$.

######  Claim 16.

If $A_{3}=\emptyset$ or $A_{4}=\emptyset$, then the robber gets captured.

###### Proof of Claim 16.

Due to symmetry, it is sufficient to show that the robber gets captured if
$A_{3}=\emptyset$. Let $A_{3}=\emptyset$. In the next turn, Cop $1$ stays at
$v_{3}$ and Cop $2$ moves to $v_{2}$. To avoid immediate capture, the robber
should move to a vertex $r^{\prime}$ that is not adjacent to $v_{2}$ and
$v_{3}$. Since $A_{1}=\emptyset$, we have $r^{\prime}\in B_{14}$. In the next
turn, Cop $1$ and Cop $2$ move to $v_{2}$ and $v_{1}$, respectively. To avoid
immediate capture, the robber must move to a vertex $r^{\prime\prime}$ that is
not adjacent to $v_{1}$ and $v_{2}$. Since $r^{\prime}\in B_{14}$, by
Observation 3.3(a), $r^{\prime\prime}\notin X$. Again since
$B_{34}=A_{3}=\emptyset$, we have $r^{\prime\prime}\in A_{4}$. Then
$\\{r^{\prime\prime},r^{\prime},v_{1},v_{2},v_{3}\\}$ induces a $P_{5}$ which
is a contradiction. So such a vertex $r^{\prime\prime}$ does not exist. Hence
the robber cannot escape from $r^{\prime}$ and gets captured. ∎

######  Claim 17.

If there exists a vertex in $B_{13}$ that is adjacent to every vertex of
$T_{3}$, then the robber gets captured.

###### Proof of Claim 17.

Let there be a vertex $b^{*}\in B_{13}$ such that $b^{*}$ is adjacent to every
vertex of $T_{3}$. If $A_{3}=\emptyset$ or $A_{4}=\emptyset$, then by Claim
16, the robber gets captured. So assume that $A_{3}\neq\emptyset$ and
$A_{4}\neq\emptyset$. Let $a\in A_{3}$ and $a^{\prime}\in A_{4}$. Recall that
Cop $1$, Cop $2$, and the robber are at $v_{3},v_{4},$ and $v_{1}$,
respectively. In the next turn, Cop $1$ and Cop $2$ move to $b^{*}$ and
$v_{3}$, respectively. To avoid immediate capture, the robber must move to a
vertex $r^{\prime}$ that is not adjacent to $b^{*}$ and $v_{3}$. Since
$A_{1}=B_{12}=\emptyset$, we have $r^{\prime}\in B_{14}\cup T_{3}$. Since
$b^{*}$ is adjacent to every vertex of $T_{3}$, $r^{\prime}\notin T_{3}$. Note
that this includes the case $T_{3}=\emptyset$. So $r^{\prime}\in B_{14}$. Now
since $\\{a^{\prime},a,v_{3},v_{2},v_{1}\\}$ does not induce a $P_{5}$, $a$ is
not adjacent to $a^{\prime}$. Note that $b^{*}$ is not adjacent to $a$;
otherwise $\\{a,b^{*},v_{1},v_{2},v_{4}\\}$ induces a $P_{5}$. Again, $b^{*}$
is adjacent to $a^{\prime}$; otherwise
$\\{a^{\prime},v_{4},v_{3},b^{*},v_{1}\\}$ induces a $P_{5}$. Similarly, we
can show that $r^{\prime}$ is adjacent to $a$ and not adjacent to
$a^{\prime}$. Now since $r^{\prime}$ is not adjacent to $b^{*}$,
$\\{a^{\prime},b^{*},v_{1},r^{\prime},a\\}$ induces a $P_{5}$, a
contradiction. So such a vertex $r^{\prime}$ does not exist. Hence the robber
cannot escape from $v_{1}$ and gets captured. ∎

We now return to the proof of Lemma 3.8. If there exists a vertex in $B_{13}$
that is adjacent to every vertex of $T_{3}$, then by Claim 17, the robber gets
captured. So we may assume that $B_{13}=\emptyset$ or every vertex of $B_{13}$
has a non-neighbor in $T_{3}$. Recall that Cop $1$, Cop $2$, and the robber
are at $v_{3},v_{4}$, and $v_{1}$, respectively. In the next turn, Cop $1$
moves to $v_{2}$ and Cop $2$ stays at $v_{4}$. To avoid immediate capture, the
robber must move to a vertex that is not adjacent to $v_{2}$ and $v_{4}$.
Hence the robber must move to a vertex in $A_{1}\cup B_{13}$. Recall that
$A_{1}=\emptyset$. Now if $B_{13}=\emptyset$, then the robber cannot escape
from $v_{1}$ and gets captured. So assume that $B_{13}\neq\emptyset$ and the
robber moves to a vertex $r_{1}\in B_{13}$. Due to our assumption, $r_{1}$ has
a non-neighbor in $T_{3}$, say $t$. Note that
$\\{t,v_{2},v_{4},v_{3},r_{1}\\}$ induces a kite and the cops and the robber
are at the positions such that the hypothesis of Lemma 3.7 holds. So by Lemma
3.7, the robber gets captured implying that $cop(G)\leq 2$. ∎

By using Lemma 3.4-3.8, we now show that the cop number of any connected
($P_{5},K_{4}$)-free graph is at most $2$.

######  Theorem 3.9.

Let $G$ be a connected $(P_{5},K_{4})$-free graph. Then $cop(G)\leq 2$.

###### Proof.

If $G$ contains an induced co-banner, then by Lemma 3.4, $cop(G)\leq 2$. So we
may assume that $G$ is co-banner-free. Now if $G$ contains an induced
butterfly, then by Lemma 3.5, $cop(G)\leq 2$. So we may further assume that
$G$ is butterfly-free. Now since $G$ is $(P_{5},K_{4},$ co-banner,
butterfly$)$-free, by Lemma 3.8, $cop(G)\leq 2$. ∎

##  4 On the class of ($P_{5},K_{3}\cup K_{1}$)-free graphs

Aigner and Fromme [1] proved that for any natural number $k$, there exists a
$C_{3}$-free graph with the cop number at least $k$. Therefore, the class of
$K_{3}\cup K_{1}$-free graphs also has unbounded cop number. However, the cop
number of a connected $K_{3}\cup K_{1}$-free graph that contains a $C_{3}$, is
at most $3$ since every $C_{3}$ dominates the graph. In the following theorem,
we show that if a connected $K_{3}\cup K_{1}$-free graph $G$ is also
$P_{5}$-free, then $cop(G)\leq 2$.

######  Theorem 4.1.

Let $G$ be a connected $(P_{5},K_{3}\cup K_{1})$-free graph. Then $cop(G)\leq
2$.

###### Proof.

If $G$ is paw-free, then by Lemma 3.1, $cop(G)\leq 2$. So we may assume that
$G$ has an induced paw, say with vertex set $P=\\{v_{1},v_{2},v_{3},v_{4}\\}$
and edge set $\\{v_{1}v_{2},v_{2}v_{3},v_{3}v_{4},v_{4}v_{2}\\}$. Define the
sets $A_{i},B_{ij},T_{i},D$, and $X$ around $P$ as defined in • ‣ 2 for every
$1\leq i,j\leq 4$ and $i<j$. Since $G$ is $K_{3}\cup K_{1}$-free, every
$C_{3}$ of $G$ is a dominating cycle of $G$. So there is no vertex at distance
at least $2$ from $P$ and hence $X=\emptyset$. Note that $A_{1}=\emptyset$;
otherwise for any $a\in A_{1}$, $\\{v_{2},v_{3},v_{4},a\\}$ induces a
$K_{3}\cup K_{1}$. Moreover, $B_{34}=\emptyset$; otherwise for any $b\in
B_{34}$, $\\{v_{1},v_{3},v_{4},b\\}$ induces a $K_{3}\cup K_{1}$. We divide
the proof into the following two cases depending on whether $B_{12}$ is empty
or not. In each case, we show that the robber gets captured by two cops after
a finite number of turns.

Case 1: $B_{12}\neq\emptyset$.

Let $b$ be a vertex of $B_{12}$. If $A_{3}\neq\emptyset$, then for any $a\in
A_{3}$, either $\\{b,v_{1},v_{2},a\\}$ induces a $K_{3}\cup K_{1}$ or
$\\{v_{4},v_{3},a,b,v_{1}\\}$ induces a $P_{5}$, a contradiction. So
$A_{3}=\emptyset$. Due to symmetry, we have $A_{4}=\emptyset$. Now if
$B_{14}\cup T_{3}\neq\emptyset$, then for any $u\in B_{14}\cup T_{3}$, either
$\\{v_{3},v_{4},u,v_{1},b\\}$ induces a $P_{5}$ or $\\{u,b,v_{1},v_{3}\\}$
induces a $K_{3}\cup K_{1}$, a contradiction. So $B_{14}\cup T_{3}=\emptyset$.
In the first turn, we place Cop $1$ and Cop $2$ at $v_{3}$ and $v_{4}$,
respectively. To avoid immediate capture, the robber should choose a vertex
$x$ that is not adjacent to $v_{3}$ and $v_{4}$. Since $A_{1}=X=\emptyset$, we
have $x\in A_{2}\cup\\{v_{1}\\}\cup B_{12}$. In the next turn, Cop $1$ stays
at $v_{3}$ and Cop $2$ moves to $v_{2}$. If the robber stays at $x$, then it
gets captured by Cop $2$. Since $A_{1}=A_{4}=B_{14}=X=\emptyset$, we have
$N[x]\subseteq N[v_{2}]\cup N[v_{3}]$. So wherever the robber moves, it gets
captured by Cop $1$ or Cop $2$.

Case 2: $B_{12}=\emptyset$.

In the first turn, we place Cop $1$ and Cop $2$ at $v_{1}$ and $v_{2}$,
respectively. To avoid immediate capture, the robber has to choose a vertex
$x$ that is not adjacent to $v_{1}$ and $v_{2}$. Since $B_{34}=X=\emptyset$,
we have $x\in A_{3}\cup A_{4}$. Due to symmetry, we may assume that $x\in
A_{3}$. In the next turn, Cop $1$ and Cop $2$ move to $v_{2}$ and $v_{4}$,
respectively. Note that $x$ does not have any neighbor in $B_{13}$; otherwise
for any neighbor $y\in B_{13}$ of $x$, $\\{x,y,v_{1},v_{2},v_{4}\\}$ induces a
$P_{5}$ in $G$. So the robber cannot move to a vertex of $B_{13}$. Moreover,
since $A_{1}=X=\emptyset$, to avoid capture, the robber should stay in
$A_{3}$. At the end of this round, suppose that the robber is at
$x^{\prime}\in A_{3}$. Note that $x^{\prime}$ may be equal to $x$. In the next
turn, Cop $1$ moves to $v_{3}$ and Cop $2$ stays at $v_{4}$. To avoid
immediate capture, the robber must move to a vertex $r$ that is not adjacent
to $v_{3}$ and $v_{4}$. Since $A_{1}=B_{12}=X=\emptyset$, we have $r\in
A_{2}$. In the next turn, Cop $1$ and Cop $2$ move to $x^{\prime}$ and
$v_{3}$, respectively. To avoid immediate capture, the robber must move to a
vertex $r^{\prime}$ that is not adjacent to $x^{\prime}$ and $v_{3}$. Since
$A_{1}=B_{12}=X=\emptyset$, we have $r^{\prime}\in A_{2}\cup A_{4}\cup
B_{14}\cup B_{24}\cup T_{3}$. Since neither
$\\{r^{\prime},r,x^{\prime},v_{3},v_{4}\\}$ nor
$\\{x^{\prime},v_{3},v_{4},r^{\prime},v_{1}\\}$ induces a $P_{5}$, we have
$r^{\prime}\notin A_{2}\cup B_{14}\cup T_{3}$. Again since
$\\{r^{\prime},v_{2},v_{4},x^{\prime}\\}$ does not induce a $K_{3}\cup K_{1}$,
we have $r^{\prime}\notin B_{24}$ and hence $r^{\prime}\in A_{4}$. In the next
turn, Cop $1$ and Cop $2$ move to $r$ and $v_{2}$, respectively. To avoid
immediate capture, the robber must move to a vertex $r^{\prime\prime}$ that is
not adjacent to $r$ and $v_{2}$. Since $A_{1}=B_{34}=X=\emptyset$ and
$r^{\prime\prime}$ is not adjacent to $v_{2}$, we have $r^{\prime\prime}\in
A_{3}\cup A_{4}\cup B_{13}\cup B_{14}\cup T_{2}$. Since
$\\{r^{\prime\prime},r^{\prime},r,v_{2},v_{1}\\}$ does not induce a $P_{5}$,
we have $r^{\prime\prime}\notin A_{3}\cup A_{4}$. Again since neither
$\\{r^{\prime},r^{\prime\prime},v_{1},v_{2},v_{3}\\}$ induces a $P_{5}$ nor
$\\{r^{\prime\prime},v_{3},v_{4},r\\}$ induces a $K_{3}\cup K_{1}$, we have
$r^{\prime\prime}\notin B_{14}\cup T_{2}$ and hence $r^{\prime\prime}\in
B_{13}$. Note that $x^{\prime}$ is not adjacent to $r^{\prime\prime}$;
otherwise $\\{x^{\prime},r^{\prime\prime},v_{1},v_{2},v_{4}\\}$ induces a
$P_{5}$. Now $\\{x^{\prime},r,r^{\prime},r^{\prime\prime},v_{1}\\}$ induces a
$P_{5}$ which is a contradiction. So such a vertex $r^{\prime\prime}$ does not
exist. Therefore, the robber cannot escape from $r^{\prime}$ and gets captured
by Cop $1$. ∎

##  5 On the class of $P_{3}\cup P_{1}$-free graphs

Let $G$ be a connected $P_{3}\cup P_{1}$-free graph. If $G$ has no induced
$P_{3}$, then $G$ is isomorphic to a complete graph and hence the domination
number of $G$ is $1$. Suppose that $G$ has an induced $P_{3}$. Then, since $G$
is $P_{3}\cup P_{1}$-free, the set of vertices of any induced $P_{3}$ of $G$
is a dominating set of $G$ and hence the domination number of $G$ is at most
$3$. This implies that the cop number of $G$ is at most $3$. In the following
theorem, we show that two cops are sufficient to capture the robber in any
connected $P_{3}\cup P_{1}$-free graph.

######  Theorem 5.1.

Let $G$ be a connected $P_{3}\cup P_{1}$-free graph. Then $cop(G)\leq 2$.

###### Proof.

Let $v\in V(G)$. In the first turn, we place both Cop $1$ and Cop $2$ at $v$.
To avoid immediate capture, the robber must choose a vertex $x$ of $G-N[v]$ if
exists. We may assume that such a vertex $x$ exists; otherwise we have
$V(G)=N[v]$ and hence $cop(G)=1$. Let $C$ be the component of $G-N[v]$ that
contains $x$. Since $G$ is $P_{3}\cup P_{1}$-free, $G-N[v]$ is $P_{3}$-free
and hence every component of $G-N[v]$ is a complete graph. In particular, $C$
is a complete graph. Since $G$ is connected, $N(C)\cap N(v)\neq\emptyset$. Let
$r\in N(C)\cap N(v)$. Note that while one of the cops stays at $v$, the robber
cannot move to a vertex of $G-V(C)$ in order to avoid immediate capture. So
for the next few turns, Cop $1$ stays at $v$ and Cop $2$ goes to a vertex of
$C$ through the vertex $r$ and captures the robber. ∎

##  6 On the class of $(P_{5},$ diamond$)$-free graphs and $2K_{1}\cup
K_{2}$-free graphs

Let $H$ be an induced subgraph of a graph $G$. A _retraction_ from $G$ to $H$
is a homomorphism from $G$ onto $H$ that maps every vertex of $H$ to itself.
Formally, a retraction from $G$ to $H$ is a mapping $\phi:V(G)\rightarrow
V(H)$ such that: $(1)$ $\phi(u)=u$ for every $u\in V(H)$ and $(2)$ if $xy\in
E(G)$, then either $\phi(x)=\phi(y)$ or $\phi(x)\phi(y)\in E(H)$. We say that
$H$ is a _retract_ of $G$ if there exists a retraction from $G$ to $H$. Note
that if $G$ is a connected graph and $H$ is a retract of $G$, then $H$ is
connected.

In this section, we prove that the cop number of any $(P_{5},$ diamond$)$-free
graph and any $(P_{5},2K_{1}\cup\leavevmode\nobreak\ K_{2})$-free graph is at
most $2$. We use the following lemma to prove these results. We note that the
lemma is an implication of a result of Berarducci and Intrigila [4]. To make
the paper self-contained, we give a proof of it.

######  Lemma 6.1 ([4]).

Let $H$ be a retract of a connected graph $G$ such that every component of
$G-V(H)$ is a complete graph. If $cop(H)\leq 2$, then $cop(G)\leq 2$.

###### Proof.

Let $\phi$ be a retraction from $G$ to $H$ and $cop(H)\leq 2$. We show that
two cops can capture the robber in the graph $G$ after a finite number of
turns. At a turn, we say that the robber’s image is at a vertex $u$ if the
image of the robber’s position is $u$ under $\phi$.

In the first turn, we place both the cops at some vertex of $H$. In the next
turn, the robber chooses a vertex of $G$ as its position. The cops first try
to capture the robber’s image by playing in the graph $H$. Note that since
$\phi$ is a homomorphism, for any move of the robber in $G$, its image has a
valid move in $H$, that is it either moves to an adjacent vertex in $H$ or
stays at the same vertex of $H$. Since $H$ is connected and the cop number of
$H$ is at most $2$, the cops capture the robber’s image after a finite number
of turns. So without loss of generality, we may assume that one of the cops,
say Cop $1$, is at the robber’s image, the other cop is at any vertex of $H$,
and it is now robber’s turn to move. Since $\phi$ is an identity mapping on
$H$, the robber is already captured if it is in $H$. So we may assume that the
robber is in $G-V(H)$. Now Cop $1$ follows the robber’s image, that is after
every turn of cops’, Cop $1$ is at the robber’s image. So to avoid immediate
capture, the robber must stay in $G-V(H)$. Hence the robber must move within a
component of $G-V(H)$, say $C$. Then Cop $2$ follows a path from its current
position to a vertex of $C$. After a finite number of turns, Cop $2$ and the
robber are in $C$ and Cop $1$ is at the robber’s image. Recall that every
component of $G-V(H)$ is a complete graph; in particular, $C$ is a complete
graph. So the robber gets captured by Cop $2$ implying that $cop(G)\leq 2$. ∎

###  6.1 $(P_{5},$ diamond$)$-free graphs

In the following theorem, we prove that the cop number of any connected
$(P_{5},$ diamond$)$-free graph is at most $2$.

######  Theorem 6.1.1.

Let $G$ be a connected $(P_{5},$ diamond$)$-free graph. Then $cop(G)\leq 2$.

###### Proof.

For the sake of contradiction, assume that there exists a counterexample of
the theorem. Let $G$ be a minimum counterexample of the theorem, that is $G$
is a connected $(P_{5},$ diamond$)$-free graph with minimum number of vertices
such that $cop(G)>2$. To proceed further, we first prove a series of claims.

######  Claim 18.

If $u$ is a vertex of $G$, then every component of $G[N(u)]$ is a complete
graph. Moreover, $G[N(u)]$ is a disconnected graph.

###### Proof of Claim 18.

Let $u$ be a vertex of $G$. Since $G$ is diamond-free, $G[N(u)]$ is
$P_{3}$-free and hence every component of $G[N(u)]$ is a complete graph. Now
for the sake of contradiction, assume that $G[N(u)]$ is connected, that is it
has only one component, say $G^{\prime}$. Note that for any $w\in
V(G^{\prime})$, $N[u]\subseteq N[w]$ since $G^{\prime}$ is a complete graph.
Define a mapping $\phi:V(G)\rightarrow V(G)\setminus\\{u\\}$ that maps $u$ to
$w$ for some $w\in V(G^{\prime})$ and maps every vertex of $G-\\{u\\}$ to
itself. Note that $\phi$ is a retraction from $G$ to $G-\\{u\\}$, that is
$G-\\{u\\}$ is a retract of $G$. Moreover, since $G$ is a minimum
counterexample, $cop(G-\\{u\\})\leq 2$. So by taking $H=G-\\{u\\}$ in Lemma
6.1, we have $cop(G)\leq 2$, a contradiction. Hence $G[N(u)]$ is a
disconnected graph. ∎

######  Claim 19.

If $u$ is a vertex of $G$, then for any vertex $v$ other than $u$,
$N(v)\setminus N[u]\neq\emptyset$.

###### Proof of Claim 19.

Let $u$ be a vertex of $G$. For the sake of contradiction, assume that there
exists a vertex $v$ other than $u$ such that $N(v)\setminus N[u]=\emptyset$,
that is $N(v)\subseteq N[u]$. Define a mapping $\phi^{\prime}:V(G)\rightarrow
V(G)\setminus\\{v\\}$ that maps $v$ to $u$ and maps every vertex of
$G-\\{v\\}$ to itself. Note that $\phi^{\prime}$ is a retraction from $G$ to
$G-\\{v\\}$, that is $G-\\{v\\}$ is a retract of $G$. Moreover, since $G$ is a
minimum counterexample, $cop(G-\\{v\\})\leq 2$. So by taking $H=G-\\{v\\}$ in
Lemma 6.1, we have $cop(G)\leq 2$, a contradiction. Hence $N(v)\setminus
N[u]\neq\emptyset$. ∎

######  Claim 20.

If $uv$ is an edge of $G$, then there exist vertices $y,z\in V(G)\setminus
N[u]$ such that $\\{u,v,y,z\\}$ induces a $P_{4}$ in $G$.

###### Proof of Claim 20.

Let $uv$ be an edge of $G$. By Claim 19, $N(v)\setminus N[u]\neq\emptyset$.
Let $G^{*}$ be a component of the graph induced by $N(v)\setminus N[u]$. By
Claim 18, every component of the graph $G[N(v)]$ is a complete graph. Hence
every component of the graph induced by $N(v)\setminus N[u]$ is a complete
graph; in particular, $G^{*}$ is a complete graph.

To prove the claim, it is sufficient to show the existence of a vertex $y\in
V(G^{*})$ that has a neighbor $z$ such that $z\notin N[\\{u,v\\}]$. For the
sake of contradiction, assume that every neighbor of every vertex of
$V(G^{*})$ is in the set $N[\\{u,v\\}]$. Then $N(V(G^{*}))\subseteq
N[\\{u,v\\}]$. Since $G^{*}$ is a component of the graph induced by
$N(v)\setminus N[u]$, we have $N(V(G^{*}))\subseteq N[u]$. Define a mapping
$\phi^{\prime\prime}:V(G)\rightarrow V(G)\setminus V(G^{*})$ that maps every
vertex of $G^{*}$ to $u$ and maps every vertex of $G-V(G^{*})$ to itself. Note
that $\phi^{\prime\prime}$ is a retraction from $G$ to $G-V(G^{*})$, that is
$G-V(G^{*})$ is a retract of $G$. Moreover, since $G$ is a minimum
counterexample, $cop(G-V(G^{*}))\leq 2$. Since $G^{*}$ is a complete graph, by
taking $H=G-V(G^{*})$ in Lemma 6.1, we have $cop(G)\leq 2$, a contradiction.
Hence the claim holds. ∎

Now we return to the proof of Theorem 6.1.1. If $G$ is $K_{4}$-free, then by
Theorem 3.9, $cop(G)\leq 2$, a contradiction. Hence $G$ must contain a
subgraph isomorphic to $K_{4}$. Let $u$ be a vertex of any induced $K_{4}$ of
$G$. Then there exists a component $G^{\prime}$ of $G[N(u)]$ such that
$|V(G^{\prime})|\geq 3$. By Claim 18, the graph $G[N(u)]$ is disconnected and
every component of $G[N(u)]$ is a complete graph. So there exists a component
$G^{\prime\prime}$ of $G[N(u)]$ other than $G^{\prime}$ and both $G^{\prime}$
and $G^{\prime\prime}$ are complete graphs. Let $v$ be a vertex of
$G^{\prime\prime}$. By Claim 20, there exist vertices $y,z\in V(G)\setminus
N[u]$ such that $\\{u,v,y,z\\}$ induces a $P_{4}$ in $G$. Note that $y$ has at
most one neighbor in $V(G^{\prime})$; otherwise
$G[V(G^{\prime})\cup\\{y,u\\}]$ contains an induced diamond. Similarly, we can
show that $z$ has at most one neighbor in $V(G^{\prime})$. Since $G^{\prime}$
and $G^{\prime\prime}$ are different components of $G[N(u)]$ and $v$ is a
vertex of $G^{\prime\prime}$, $v$ does not have any neighbor in
$V(G^{\prime})$. Now since $|V(G^{\prime})|\geq 3$, there exists a vertex
$x\in V(G^{\prime})$ such that $x$ is not adjacent to $v,y,$ and $z$. Then
$\\{x,u,v,y,z\\}$ induces a $P_{5}$ in $G$, a contradiction. So we may
conclude that such a graph $G$ does not exist. This completes the proof of
Theorem 6.1.1. ∎

###  6.2 $2K_{1}\cup K_{2}$-free graphs

Let $G$ be a connected $2K_{1}\cup K_{2}$-free graph and $uv$ be an edge of
$G$. If $\\{u,v\\}$ is a dominating set of $G$, then $cop(G)\leq 2$. If
$\\{u,v\\}$ is not a dominating set of $G$, then there exists a vertex $z$
that is not adjacent to $u$ and $v$. Now since $G$ is $2K_{1}\cup K_{2}$-free,
$\\{u,v,z\\}$ is a dominating set of $G$. So the cop number of $G$ is at most
$3$. Therefore, the cop number of any $2K_{1}\cup K_{2}$-free graph is at most
$3$. Turcotte [18] showed the existence of $2K_{1}\cup K_{2}$-free graphs
having the cop number $3$ with computer aided graph search. So the cop number
of the class of $2K_{1}\cup K_{2}$-free graphs is $3$. Note that any complete
multipartite graph is $K_{1}\cup K_{2}$-free. Now consider a $K_{1}\cup
K_{2}$-free graph $G$. Since $G^{c}$ is $P_{3}$-free, $G^{c}$ is a disjoint
union of complete graphs. So $G$ is a complete multipartite graph. Hence we
may conclude that a graph $G$ is $K_{1}\cup K_{2}$-free if and only if $G$ is
a complete multipartite graph.

######  Theorem 6.2.1.

Let $G$ be a connected $(P_{5},2K_{1}\cup K_{2})$-free graph. Then $cop(G)\leq
2$.

###### Proof.

For the sake of contradiction, assume that there exists a counterexample of
the theorem. Let $G$ be a minimum counterexample of the theorem, that is $G$
is a connected $(P_{5},2K_{1}\cup K_{2})$-free graph with minimum number of
vertices such that $cop(G)>2$. Let $u$ be a vertex of $G$ and $G^{\prime}$ be
the graph $G-N[u]$. Since $G$ is $2K_{1}\cup K_{2}$-free, $G^{\prime}$ is a
$K_{1}\cup K_{2}$-free graph. Hence $G^{\prime}$ is a complete multipartite
graph, say with $k$ parts. We first show that $k\geq 2$. If possible, then let
$k\leq 1$. If $k=0$, then $\\{u\\}$ is a dominating set of $G$ implying that
$cop(G)=1$, a contradiction. So $k=1$. Then $G^{\prime}$ consists of only
isolated vertices. We show that two cops can capture the robber to obtain a
contradiction to the fact that $cop(G)>2$. We place both the cops at $u$. The
robber must choose a vertex of $G^{\prime}$ to avoid immediate capture. While
one cop stays at $u$, the robber cannot move since $G^{\prime}$ consists of
only isolated vertices. Then the second cop can go and capture the robber in
the graph $G^{\prime}$. Hence we have $k\geq 2$. Now if there exists a partite
set $S$ of $G^{\prime}$ such that $|S|=1$, then $\\{u\\}\cup S$ is a
dominating set of $G$ implying that $cop(G)\leq 2$, a contradiction. So we may
assume that every partite set of $G^{\prime}$ has cardinality at least $2$.

######  Claim 21.

If $v$ is a neighbor of $u$, then $v$ has at most one non-neighbor in
$V(G^{\prime})$.

###### Proof of Claim 21.

Let $v$ be a neighbor of $u$. For the sake of contradiction, assume that $v$
has two non-neighbors in $V(G^{\prime})$, say $x$ and $y$. Since
$\\{u,v,x,y\\}$ does not induce a $2K_{1}\cup K_{2}$ in $G$, $x$ and $y$ are
in different partite sets of the complete multipartite graph $G^{\prime}$.
Recall that every partite set of $G^{\prime}$ has cardinality at least $2$.
Let $x^{\prime}$ be a vertex of $G^{\prime}$ other than $x$ such that $x$ and
$x^{\prime}$ are in the same partite set of $G^{\prime}$. Note that $v$ is
adjacent to $x^{\prime}$; otherwise $\\{u,v,x,x^{\prime}\\}$ induces a
$2K_{1}\cup K_{2}$ in $G$. Since $y$ and $x^{\prime}$ are in different partite
sets of the complete multipartite graph $G^{\prime}$, $y$ is adjacent to
$x^{\prime}$. Similarly, $y$ is adjacent to $x$. Then
$\\{u,v,x^{\prime},y,x\\}$ induces a $P_{5}$ in $G$, a contradiction. So $v$
has at most one non-neighbor in $V(G^{\prime})$. ∎

######  Claim 22.

If $z$ is a vertex of $G^{\prime}$, then $z$ has a non-neighbor in $N(u)$.

###### Proof of Claim 22.

Let $z$ be a vertex of $G^{\prime}$. For the sake of contradiction, assume
that $z$ is adjacent to every vertex of $N(u)$, that is $N(u)\subseteq N(z)$.
Define a mapping $\phi:V(G)\rightarrow V(G)\setminus\\{u\\}$ that maps $u$ to
$z$ and maps every vertex of $G-\\{u\\}$ to itself. Note that $\phi$ is a
retraction from $G$ to $G-\\{u\\}$. Moreover, since $G$ is minimum
counterexample, $cop(G-\\{u\\})\leq 2$. By taking $H=G-\\{u\\}$ in Lemma 6.1,
we have $cop(G)\leq 2$, a contradiction. So $z$ has non-neighbor in $N(u)$. ∎

Now we show that two cops can capture the robber in $G$. Let $v$ be a neighbor
of $u$. In the first turn, we place Cop $1$ at $u$ and Cop $2$ at $v$. To
avoid immediate capture, the robber must choose a vertex $x$ that is not
adjacent to $u$ and $v$. Since $x\notin N[u]$, $x\in G^{\prime}$. Again since
$x$ is not adjacent to $v$, by Claim 21, $x$ is the only non-neighbor of $v$
in $V(G^{\prime})$, that is $v$ is adjacent to every vertex of
$V(G^{\prime})\setminus\\{x\\}$. Since every partite set of $G^{\prime}$ has
cardinality at least $2$, there exists a vertex $x^{\prime}$ other than $x$
such that $x$ and $x^{\prime}$ are in the same parite set of $G^{\prime}$. By
Claim 22, $x^{\prime}$ has a non-neighbor $r$ in $N(u)$. Again by Claim 21,
$r$ is adjacent to every vertex of $G^{\prime}$ except $x^{\prime}$. In
particular, $r$ is adjacent to $x$.

In the next turn, Cop $1$ moves to $r$ and Cop $2$ moves to $u$. To avoid
immediate capture, the robber must move to a vertex that is not adjacent to
$r$ and $u$. Since $x^{\prime}$ is the only vertex that is not adjacent to $r$
and $u$, the robber must move to $x^{\prime}$. This is not possible since $x$
and $x^{\prime}$ are in the same partite set of the multipartite graph
$G^{\prime}$. So the robber cannot escape from $x$ and gets captured implying
that $cop(G)\leq 2$, a contradiction. So such a graph $G$ does not exist. This
completes the proof of Theorem 6.2.1. ∎

##  7 Conclusion

In this paper, we obtained strategies using two cops to capture the robber in
a $(P_{5},H)$-free graph, where $H\in\\{C_{4}$, $C_{5}$, claw, diamond, paw,
$K_{4}$, $2K_{1}\cup K_{2}$, $K_{3}\cup K_{1}$, $P_{3}\cup P_{1}\\}$. On the
other hand, $P_{4}$-free graphs and $2K_{2}$-free graphs are already known to
have the cop number at most $2$. By including these results, we conclude that
the cop number of $(P_{5},\mathcal{H})$-free graphs is at most $2$, where
$\mathcal{H}$ is any graph on $4$ vertices with at least one edge. Moreover,
$C_{4}$ and $C_{5}$ have the cop numbers $2$ and at least one of these belongs
to the class of $(P_{5},\mathcal{H})$-free graphs. Thus the cop number of this
class is $2$. Note that Conjecture 1.1 remains open even for $t=5$. Even the
question whether $2$ cops are sufficient to capture the robber in a
$P_{5}$-free graph with independence number at most $3$, remains open.
Although we have focused on the subclasses of $P_{5}$-free graphs, the methods
we have used may be applied to obtain the cop number of some other graph
classes with forbidden induced subgraphs.

## References

  * [1] M. Aigner, M. Fromme,  A game of cops and robbers,  Discrete Appl. Math. 8 (1984) 1–12.
  * [2] T. Andreae,  Note on a pursuit game played on graphs,  Discrete Appl. Math. 9 (1984) 111–115.
  * [3] W. Baird, A. Bonato,  Meyniel’s conjecture on the cop number: A survey,  J. Combin. 3 (2012) 225–238.
  * [4] A. Berarducci, B. Intrigila,  On the cop number of a graph,  Adv. in Appl. Math. 14 (1993) 389–403.
  * [5] N. E. Clarke,  Constrained cops and robber,  Ph.D. Thesis, Dalhousie University, 2002.
  * [6] N. E. Clarke, G. MacGillivray,  Characterizations of $k$-copwin graphs,  Discrete Math. 312 (2012) 1421–1425.
  * [7] F. V. Fomin, P. A. Golovach, J. Kratochvíl, N. Nisse, K. Suchan,  Pursuing a fast robber on a graph,  Theoret. Comput. Sci. 411 (2010) 1167–1181.
  * [8] P. Frankl,  Cops and robbers in graphs with large girth and Cayley graphs,  Discrete Appl. Math. 17 (1987) 301–305.
  * [9] G. Joret, M. Kamiński, D. O. Theis,  The cops and robber game on graphs with forbidden (induced) subgraphs,  Contributions to Discrete Math. 5 (2010) 40–51.
  * [10] A. Kosowski, B. Li, N. Nisse, K. Suchan,  $k$-chordal graphs: From cops and robber to compact routing via treewidth,  Algorithmica 72 (2015) 758–777.
  * [11] M. Liu,  The cop number of graphs with forbidden induced subgraphs,  (2019) arXiv:1908.11478v1.
  * [12] L. Lu, X. Peng,  On Meyniel’s conjecture of the cop number,  J. Graph Theory 71 (2012) 192–205.
  * [13] M. Masjoodi, L. Stacho,  Cops and robbers on graphs with a set of forbidden induced subgraphs,  Theoret. Comput. Sci. 839 (2020) 186–194.
  * [14] R. Nowakowski, P. Winkler,  Vertex to vertex pursuit in a graph,  Discrete Math. 43 (1983) 235–239.
  * [15] A. Scott, B. Sudakov,  A bound for the cops and robbers problem,  SIAM J. Discrete Math. 25 (2011) 1438–1442.
  * [16] V. Sivaraman,  An application of the Gyárfás path argument,  Discrete Math. 342 (2019) 2306–2307.
  * [17] V. Sivaraman, S. Testa,  Cop number of $2K_{2}$-free graphs,  (2019) arXiv:1903.11484v1.
  * [18] J. Turcotte,  Cops and robber on $2K_{2}$-free graphs,  Discrete Math. 345 (2022) 112660.
  * [19] A. Quilliot,  Jeux et points fixes sur les graphes,  Thèse de 3ème cycle, Université de Paris VI, 1978.
  * [20] Z. A. Wagner,  Cops and robbers on diameter two graphs,  Discrete Math. 338 (2015) 107–109.