Discrete Lunch‎ > ‎

1st Discrete Lunch: Cops & Robber game and genus of a graph

posted Aug 8, 2013, 7:45 AM by Dirk Oliver Theis   [ updated Aug 8, 2013, 7:54 AM ]
Mon June 3, 2013.
DOT explained the Cops & Robber game which is played on graphs.  The cop number is the smallest number of cops which are needed for the cops to have a winning strategy.
An old theorem of Aigner & Fromme says that the maximum cop number of any planar graph is 3.
More generally, for graphs embedded in surfaces, one wants to know the dependence of the cop number on the genus.  There are bad gaps between upper and lower bounds.  Already for toroidal graphs, it is not known whether the maximum cop number is 3 or 4.  In general, if the genus of the graph is g the upper bounds on the maximum cop number of all graphs with genus g is O(g) --- the best known constant in the big-O is 3/2 ---, the lower bounds are around g^(1/2).