# Cops, robbers, and infinite graphs (Seminar DM)

### Iz MaFiRaWiki

**Cops, robbers, and infinite graphs**

Florian Lehner

Torek, 20. januarja 2015, od 10h do 12h, Plemljev seminar, Jadranska 19

**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.