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

copnumbergenusretractiontoroidal graph

Mathematics Subject Classification ID

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

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

(19)

• On the cop number of toroidal graphs
• 4-cop-win graphs have at least 19 vertices
• The game of cops and eternal robbers
• A simple method for proving lower bounds in the zero-visibility cops and robber game
• 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?)
• Bounding the cop number of a graph by its genus
• Conjectures on cops and robbers
• Cops and robber on some families of oriented graphs
• The node cop‐win reliability of unicyclic and bicyclic graphs
• The localization number of designs
• Guarding isometric subgraphs and cops and robber in planar graphs
• Improved bounds on the cop number of a graph drawn on a surface
• Cops and robbers on 1-planar graphs
• Bounding the cop number of a graph by its genus
• Improved bounds on the cop number when forbidding a minor
• The game of cops and robber on geodesic spaces
• On 1-planar graphs with bounded cop-number
• Cops and robbers for graphs on surfaces with crossings

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)