Abstrakt
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.