Cops and Robbers on Intersection Graphs

The game of cops and robber, introduced by Nowakowski and Winkler in 1983, is played by two players on a graph

G

, one controlling

k

cops and the other one robber, all positioned on

V

G

. The players alternate in moving their pieces to distance at most 1 each. The cops win if they capture the robber, the robber wins by escaping indefinitely. The cop-number of

G

, that is the smallest

k

such that

k

cops win the game, has recently been a widely studied parameter.

Intersection graph classes are defined by their geometric representations: the vertices are represented by certain geometrical shapes and two vertices are adjacent if and only if their representations intersect. Some well-known intersection classes include interval and string graphs. Various properties of many of these classes have been studied recently, including an interest in their game-theoretic properties.

In this paper we show an upper bound on the cop-number of string graphs and sharp bounds on the cop-number of interval filament graphs, circular graphs, circular arc graphs and function graphs. These results also imply polynomial algorithms determining cop-number for all these classes and their sub-classes.