Florian Lehner: Cops, robbers, and infinite graphs

Povzetek. Pursuit-evasion based searching, also known as the game of cops and robbers, is a game on a graph between two players, C (the cop) and R (the robber). The rules are as follows: In the first round both C and R choose a starting vertex, in each consecutive round they are allowed to move to a neighboring vertex. The cop wins the game, if after some finite number of steps C and R occupy the same vertex, otherwise the robber wins.

A basic question related to this game is to characterize the class of graphs for which the cop has a winning strategy. For finite graphs it has been shown by Nowakowski and Winkler that these are exactly the constructible graphs.

For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they believed the same to be true. We disprove this conjecture and suggest a further modification in the same spirit for which we can show that the cop has a winning strategy on every constructible graph.