Predavatelj: Florian Lehner (TU Graz, Avstrija)
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 these are exactly the constructible graphs.
For infinite graphs, Chastand et al introduced a modification of the winning criterion for which they conjectured the same to be true. We disprove this conjecture and suggest a further modification in the same spirit for which we show that the cop has a winning strategy on every constructible graph.
