The cop number of the one-cop-moves game on planar graphs.

*(English)*Zbl 06852645
Gao, Xiaofeng (ed.) et al., Combinatorial optimization and applications. 11th international conference, COCOA 2017, Shanghai, China, December 16–18, 2017. Proceedings. Part II. Cham: Springer (ISBN 978-3-319-71146-1/pbk; 978-3-319-71147-8/ebook). Lecture Notes in Computer Science 10628, 199-213 (2017).

Summary: Cops and robbers is a vertex-pursuit game played on graphs. In the classical cops-and-robbers game, a set of cops and a robber occupy the vertices of the graph and move alternately along the graph’s edges with perfect information about each other’s positions. If a cop eventually occupies the same vertex as the robber, then the cops win; the robber wins if she can indefinitely evade capture. Aigner and Frommer established that in every connected planar graph, three cops are sufficient to capture a single robber. In this paper, we consider a recently studied variant of the cops-and-robbers game, alternately called the one-active-cop game, one-cop-moves game or the lazy-cops-and-robbers game, where at most one cop can move during any round. We show that Aigner and Frommer’s result does not generalise to this game variant by constructing a connected planar graph on which a robber can indefinitely evade three cops in the one-cop-moves game. This answers a question recently raised by Sullivan, Townsend and Werzanski.

For the entire collection see [Zbl 1378.68013].

For the entire collection see [Zbl 1378.68013].