2026-08-06T03:48:14Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17330 2024-03-06T10:59:28Z ddc:004 open_access

On the Cop Number of String Graphs Das, Sandip Gahlawat, Harmender Cop number string graphs intersection graphs planar graphs pursuit-evasion games 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. We show that the cop number of a string graph is at most 13, improving upon a result of Gavenčiak 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, addressing an open question of Gromovikov et al. [Austr. J. Comb. 76(2), 248-265 (2020)]. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sandip Das and Harmender Gahlawat 2022 Is Part Of LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ISAAC.2022.45 urn:nbn:de:0030-drops-173308 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.45 eng https://creativecommons.org/licenses/by/4.0/legalcode