Prof. Emo Welzl and Prof. Bernd Gärtner
|Mittagsseminar Talk Information|
Date and Time: Thursday, February 07, 2013, 12:15 pm
Duration: 45 minutes
Location: CAB G51
Speaker: Daniel Graf
The game of cops and robbers is played on the vertices of some fixed graph G. Turn by turn one or several cops and a single robber move along the edges of G. The cops win if they capture the robber. The cop number of G is the minimum number of cops needed to win the game.
A long time ago H. Meyniel conjectured that O(n^(1/2)) cops are enough for any connected G on n vertices. M. Aigner and M. Fromme showed that 3 cops are enough for any planar graph. A recent upper bound for general graphs by A. Scott and B. Sudakov improves on several previous results.
In this talk I present an analysis of the game with a single cop as well as several lower and upper bounds on the cop number.
Automatic MiSe System Software Version 1.4803M | admin login