Topological directions in cops and robbers

DOI10.4310/JOC.2020.V11.N1.A3zbMATH Open1427.05144arXiv1709.09050WikidataQ127198452 ScholiaQ127198452MaRDI QIDQ2335907FDOQ2335907

Anthony Bonato, Bojan Mohar

Publication date: 18 November 2019

Published in: Journal of Combinatorics (Search for Journal in Brave)

Abstract: We survey results at the intersection of topological graph theory and the game of Cops and Robbers, focusing on results, conjectures, and open problems for the cop number of a graph embedded on a surface. After a discussion on results for planar graphs, we consider graphs of higher genus. In 2001, Schroeder conjectured that if a graph has genus $g,$ then its cop number is at most $g+3.$ While Schroeder's bound is known to hold for planar and toroidal graphs, the case for graphs with higher genus remains open. We consider the capture time of graphs on surfaces and examine results for embeddings of graphs on non-orientable surfaces. We present a conjecture by the second author, and in addition, we survey results for the lazy cop number, directed graphs, and Zombies and Survivors.

Full work available at URL: https://arxiv.org/abs/1709.09050

zbMATH Keywords

genusretractiontoroidal graphcopnumber

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cited In (12)

• Guarding isometric subgraphs and cops and robber in planar graphs
• The game of cops and eternal robbers
• Bounding the Cop Number of a Graph by Its Genus
• Improved bounds on the cop number of a graph drawn on a surface
• On the cop number of toroidal graphs
• Cops and robbers on 1-planar graphs
• The localization number of designs
• 4-cop-win graphs have at least 19 vertices
• Cops and robber on some families of oriented graphs
• The node cop‐win reliability of unicyclic and bicyclic graphs
• Improved bounds on the cop number when forbidding a minor
• A simple method for proving lower bounds in the zero-visibility cops and robber game

This page was built for publication: Topological directions in cops and robbers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2335907)