The PIMS Postdoctoral Fellow Seminar: Alice Lacaze-Masmonteil

The game of Cops and Robber played on graphs is a turn-based game between a set of $k \geqslant 1$ cops and a single robber. Cops and robber alike sit on the vertices of the graph with the cops first selecting their starting vertices. At the beginning of their turn, each cop may move to an adjacent vertex; likewise for the robber. The cops' objective is to capture the robber by having one of their number sit on the same vertex as the robber; the robber seek to avoid capture. Given a graph $G$, $k$ cops have a winning strategy on $G$ if they can guarantee the robber's capture within a finite number of turns. Of particular interest is the \emph{cop number} of a graph $G$ which is the minimum number of cops for which there exists a winning strategy on $G$. Since the introduction of the game of Cops and Robber, numerous variations of the game have been introduced. In this talk, I will focus on a variant of this game introduced by Bonato et al.~(2013) known as the game of Cops and Attacking Robber. In this case, we follow the same rules as the original game except that the robber is now given the ability to attack an adjacent cop at the beginning of his turn, thereby removing this cop from play. I will discuss some result on open problems of Bonato et al.~(2013). This is joint work with Florian Brendle, Alex Clow, and Torsten Ueckerdt.