Anthony Bonato (30/06/16)

Sigurður Örn Stefánsson, júní 27, 2016

Málstofa í stærðfræði

Fyrirlesari: Anthony Bonato
Titill: Conjectures on Cops and Robbers Games on Graphs

Staðsetning: TG-227 (Tæknigarður, 2. hæð)
Tími: Fimmtudagur 30. júní kl. 13:20.


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.