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.

Ágrip:

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.