Cops and Attacking Robbers with Cycle Constraints

This paper considers the Cops and Attacking Robbers game, a variant of Cops and Robbers, where the robber is empowered to attack a cop in the same way a cop can capture the robber. In a graph $G$, the number of cops required to capture a robber in the Cops and Attacking Robbers game is denoted by $\text{attCop}(G)$. We characterise the triangle-free graphs $G$ with $\text{attCop}(G)\le 2$ via a natural generalisation of the cop-win characterisation by Nowakowski and Winkler \cite{nowakowski1983vertex}. We also prove that all bipartite planar graphs $G$ have $\text{attCop}(G)\le 4$ and show this is tight by constructing a bipartite planar graph $G$ with $\text{attCop}(G)=4$. Finally we construct $17$ non-isomorphic graphs $H$ of order $58$ with $\text{attCop}(H)=6$ and $\text{cop}(H)=3$. This provides the first example of a graph $H$ with $\text{attCop}(H)-\text{cop}(H)\ge 3$ extending work by Bonato, Finbow, Gordinowicz, Haidar, Kinnersley, Mitsche, Prałat, and Stacho \cite{bonato2014robber}. We conclude with a list of conjectures and open problems.