Tata Institute of Fundamental Research

Catch them if you can

STCS Student Seminar
Speaker: Juhi Chaudhary (TIFR)
Organiser: Agniv Bandyopadhyay
Date: Saturday, 20 Jul 2024, 14:30 to 15:30
Venue: A-201 (STCS Seminar Room)

(Scan to add to calendar)
Abstract: 

The Cops and Robber game is a well-studied two-player pursuit-evasion game played on graphs, where a team of cops attempts to capture a robber. The cop number of a graph represents the minimum number of cops required for a successful capture. Graphs with a cop number of one are known as cop-win graphs. In this seminar, I will begin by characterizing cop-win graphs. Subsequently, I will demonstrate, using the technique of guarding a subgraph—a method for bounding the cop number of graphs with geometric representations—that the cop number for planar graphs is atmost three.