On the cop number of toroidal graphs

DOI10.1016/J.JCTB.2021.06.008zbMATH Open1473.05205arXiv1904.07946OpenAlexW3181621922MaRDI QIDQ1984519FDOQ1984519

Florian Lehner

Publication date: 16 September 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: We show that the cop number of toroidal graphs is at most 3. This resolves a conjecture by Schroeder from 2001 which is implicit in a question by Andreae from 1986.

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

zbMATH Keywords

games on graphscops and robberpursuit-evasion gamecombinatorial came

Mathematics Subject Classification ID

Games on graphs (graph-theoretic aspects) (05C57) Games involving graphs (91A43) Positional games (pursuit and evasion, etc.) (91A24)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Vertex-to-vertex pursuit in a graph
• A game of cops and robbers
• Meyniel's conjecture on the cop number: a survey
• A short note about pursuit games played on a graph with a given genus
• On a pursuit game played on graphs for which a minor is excluded
• A note on the cops and robber game on graphs embedded in non-orientable surfaces
• Topological directions in cops and robbers

Cited In (11)

• Chasing a drunk robber in many classes of graphs
• Cops and robber on butterflies, grids, and AT-free graphs
• Bounding the Cop Number of a Graph by Its Genus
• Vertex arboricity of toroidal graphs with a forbidden cycle
• 4-cop-win graphs have at least 19 vertices
• The pagenumber of toroidal graphs is at most seven
• Title not available (Why is that?)
• On the cop number of graphs of high girth
• Improved bounds on the cop number when forbidding a minor
• When the Comaximal Graph of a Lattice is Toroidal
• On enumeration of a class of toroidal graphs

This page was built for publication: On the cop number of toroidal graphs

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