Anthony Bonato (30/06/16)

Math Colloquium

Speaker: Anthony Bonato
Title: Conjectures on Cops and Robbers Games on Graphs

Location: TG-227 (Tæknigarður, 2nd floor)
Time: Thursday, June 30 at 13:20.

Abstract:

The game of Cops and Robbers gives rise to a rich set of conjectures, mainly associated with the cop number of a graph. Arguably the most important such conjecture is Meyniel’s, which posits a \(O(n^{1/2})\) upper bound on the cop number of a connected graph of order n. We discuss the state-of-the-art on Meyniel’s conjecture, and explore other conjectures on cop number ranging from topics within computational, probabilistic, and topological graph theory.