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

When

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

Where

Room TH:A-1247

Thákurova 7, Prague 6

Record

YouTube

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

Abstract

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.

The person responsible for the content of this page: Bc. Veronika Dvořáková