Document Open Access Logo

On the Cop Number of String Graphs

Authors Sandip Das, Harmender Gahlawat

PDF
Thumbnail PDF

File

LIPIcs.ISAAC.2022.45.pdf
  • Filesize: 0.9 MB
  • 18 pages

Document Identifiers

Author Details

Sandip Das
  • Indian Statistical Institute, Kolkata, India
Harmender Gahlawat
  • Ben-Gurion University of the Negev, Beer-Sheva, Israel

Funding

This research was financed by the IFCAM project "Applications of graph homomorphisms" (MA/IFCAM/18/39).
  • Gahlawat, Harmender: Supported by the Israel Science Foundation (ISF) grant no. 1176/18

Acknowledgements

We thank Uma kant Sahoo, Dibyayan Chakraborty, and Florent Foucaud for initial discussions on the topic of this paper.

Cite AsGet BibTex

Sandip Das and Harmender Gahlawat. On the Cop Number of String Graphs. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 45:1-45:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ISAAC.2022.45

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. 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)].

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Graph algorithms
Keywords
  • Cop number
  • string graphs
  • intersection graphs
  • planar graphs
  • pursuit-evasion games

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. I. Abraham, C. Gavoille, A. Gupta, O. Neiman, and K. Talwar. Cops, robbers, and threatening skeletons: Padded decomposition for minor-free graphs. SIAM Journal on Computing, 48(3):1120-1145, 2019. URL: https://doi.org/10.1137/17M1112406.
  2. I. Adler. Marshals, monotone marshals, and hypertree-width. Journal of Graph Theory, 47(4):275-296, 2004. Google Scholar
  3. M. Aigner and M. Fromme. A game of cops and robbers. Discrete Applied Mathematics, 8(1):1-12, 1984. Google Scholar
  4. T. Andreae. On a pursuit game played on graphs for which a minor is excluded. Journal of Combinatorial Theory Series B, 41(1):37-47, 1986. Google Scholar
  5. A. Asinowski, E. Cohen, M.C. Golumbic, V. Limouzy, M. Lipshteyn, and M. Stern. Vertex intersection graphs of paths on a grid. Journal of Graph Algorithms and Applications, 16(2):129-150, 2012. Google Scholar
  6. A. Berarducci and B. Intrigila. On the cop number of a graph. Advances in Applied mathematics, 14(4):389-403, 1993. Google Scholar
  7. A. Beveridge, A. Dudek, A. Frieze, and T. Müller. Cops and robbers on geometric graphs. Combinatorics, Probability and Computing, 21(6):816-834, 2012. Google Scholar
  8. A. Bonato and R. Nowakowski. The Game of Cops and Robbers on Graphs. American Mathematical Society, 2011. Google Scholar
  9. N. Bowler, J. Erde, F. Lehner, and M. Pitz. Bounding the cop number of a graph by its genus. SIAM Journal on Discrete Mathematics, 35(4):2459-2489, 2021. Google Scholar
  10. S. Brandt, S. Pettie, and S. Uitto. Fine-grained lower bounds on cops and robbers. In Yossi Azar, Hannah Bast, and Grzegorz Herman, editors, 26th Annual European Symposium on Algorithms (ESA 2018), volume 112 of Leibniz International Proceedings in Informatics (LIPIcs), pages 9:1-9:12, Dagstuhl, Germany, 2018. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.9.
  11. F. Fomin, P. Golovach, J. Kratochvíl, N. Nisse, and K. Suchan. Pursuing a fast robber on a graph. Theoretical Computer Science, 41(7-9):1167-1181, 2010. Google Scholar
  12. J. Fox and J. Pach. A separator theorem for string graphs and its applications. In S. Das and Uehara R., editors, WALCOM: Algorithms and Computation, volume 5431 of Lecture Notes in Computer Science(LNCS), pages 1-14, Berlin, Heidelberg, 2009. Springer. URL: https://doi.org/10.1007/978-3-642-00202-1_1.
  13. T. Gavenčiak, P. Gordinowicz, V. Jelínek, P. Klavík, and J. Kratochvíl. Cops and robbers on intersection graphs. European Journal of Combinatorics, 72:45-69, 2018. Google Scholar
  14. A. C. Giannopoulou, P. Hunter, and D. M. Thilikos. Lifo-search: A min–max theorem and a searching game for cycle-rank and tree-depth. Discrete Applied Mathematics, 160(15):2089-2097, 2012. Google Scholar
  15. D. Gonçalves, L. Isenmann, and C. Pennarun. Planar graphs as l-intersection or l-contact graphs. In SODA, pages 172-1844, 2018. Google Scholar
  16. I. Gromovikov, W. B. Kinnersleyb, and B. Seamone. Fully active cops and robbers. Australian Journal of Combinatorics, 76(2):248-265, 2020. Google Scholar
  17. T. Johnson, N. Robertson, P. D. Seymour, and R. Thomas. Directed tree-width. Journal of Combinatorial Theory Series B, 82(1):138-154, 2001. Google Scholar
  18. W. B. Kinnersley. Cops and robbers is exptime-complete. Journal of Combinatorial Theory Series B, 111:201-220, 2015. Google Scholar
  19. A. V. Kostochka and J. Nešetřil. Coloring relatives of intervals on the plane, i: Chromatic number versus girth. European Journal of Combinatorics, 19(1):103-110, 1998. Google Scholar
  20. F. Lehner. On the cop number of toroidal graphs. Journal of Combinatorial Theory, Series B, 151:250-262, 2021. Google Scholar
  21. M. Mamino. On the computational complexity of a game of cops and robbers. Theoretical Computer Science, 477:48-56, 2013. Google Scholar
  22. R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph. Discrete Mathematics, 43(2-3):235-239, 1983. Google Scholar
  23. J. Pach and G. Toth. How many ways can one draw a graph? In GD, pages 47-58. Springer, 2003. Google Scholar
  24. T. D. Parsons. Pursuit-evasion in a graph. In Theory and Applications of Graphs, LNCS, volume 642, pages 426-441. Springer, 1978. Google Scholar
  25. A. Pawlik, J. Kozik, T. Krawczyk, M. Lasoń, P. Micek, W. T. Trotter, and B. Walczak. Triangle-free intersection graphs of line segments with large chromatic number. Journal of Combinatorial Theory Series B, 105:6-10, 2014. Google Scholar
  26. J. Petr, J. Portier, and L. Versteegen. A faster algorithm for cops and robbers. arXiv, 2021. URL: http://arxiv.org/abs/2112.07449v2.
  27. A. Quilliot. Thése d'Etat. PhD thesis, Université de Paris VI, 1983. Google Scholar
  28. A. Quilliot. A short note about pursuit games played on a graph with a given genus. Journal of Combinatorial Theory Series B, 38(1):89-92, 1985. Google Scholar
  29. B. S. W. Schroeder. The copnumber of a graph is bounded by⌊ 3/2*genus(g)⌋ + 3. In Categorical perspectives. Trends in mathematics, pages 243-263, 2001. Google Scholar
  30. P. D. Seymour and R. Thomas. Graph searching and a min-max theorem for tree-width. Journal of Combinatorial Theory Series B, 58(1):22-33, 1993. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact