String Graph with Cop Number 4
Stéphane Durocher, Myroslav Kryven, Maarten Löffler, Sub Music Information Computing, Geometric Computing, Stefan Felsner, Karsten Klein · Utrecht University Repository (Utrecht University) · 2024
Cops and Robbers is a well-studied pursuit-evasion game in which a set of cops seeks to catch a robber in a graph G, where cops and the robber move along edges of G. The cop number of G is the minimum number of cops that is sufficient to catch the robber. The game of Cops and Robbers has been well-studied on beyond-planar graphs (that is, graphs that can be drawn with only few crossings) [1, 4] as well as intersection graphs (that is, graphs where the vertices represent geometric objects, and an edge exists between two vertices if the corresponding objects intersect). We consider a well-known subclass of intersection graphs called string graphs where the objects are curves. So far no string graph with cop number larger than three was known. We construct the first string graph with cop number four, which improves the previous bound and answers an open question by Gavenčiak et al. [5].