G²OAT seminar: On the cop number of string graphs


5. 6. 2023
13:00 – 14:00


Room TH:A-1247

Thákurova 7, Prague 6



Harmender Gahlawat from the Ben-Gurion University of the Negev will speak at the regular Monday seminar of the G²OAT group. During his talk, he will discuss the topic of determining the minimum number of cops for the Cops and Robber game on string graphs.

Event website


Cops and Robber is a well-studied two-player pursuit-evasion game played on a graph, where a group of cops tries to capture the robber. The cop number of a graph is the minimum number of cops required to capture the robber. Guarding a subgraph is a technique that is very useful in bounding the cop number of graphs having a geometric representation. In this talk, first, we will survey some results obtained using guarding subgraphs. Then, as an application of guarding isometric paths, we show that the cop number of a string graph is at most 13, improving upon a result of Gavenciak et al.~[Eur. J. of Comb. 72, 45–69 (2018)]. Using similar techniques, we also show that four cops have a winning strategy for a variant of Cops and Robber, named Fully Active Cops and Robber, on planar graphs.