Topological directions in cops and robbers

DOI10.4310/JOC.2020.V11.N1.A3MaRDI QIDQ2335907zbMATH OpenWikidataFDO

Authors Bojan Mohar, Anthony Bonato

Publication date 18 November 2019

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

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)

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.

Recommendations

• A note on the cops and robber game on graphs embedded in non-orientable surfaces
• Bounding the cop number of a graph by its genus
• Meyniel's conjecture on the cop number: a survey
• Conjectures on cops and robbers
• scientific article; zbMATH DE number 1665333

Cited in

(16)

• Guarding isometric subgraphs and cops and robber in planar graphs
• The game of cops and eternal robbers
• On the cop number of toroidal graphs
• Improved bounds on the cop number of a graph drawn on a surface
• Cops and robbers on 1-planar graphs
• 4-cop-win graphs have at least 19 vertices
• The localization number of designs
• Bounding the cop number of a graph by its genus
• Bounding the cop number of a graph by its genus
• A note on the cops and robber game on graphs embedded in non-orientable surfaces
• scientific article; zbMATH DE number 1665333 (Why is no real title available?)
• Cops and robber on some families of oriented graphs
• Conjectures on cops and robbers
• 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)