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.