On a pursuit game played on graphs for which a minor is excluded

DOI10.1016/0095-8956(86)90026-2zbMath0641.90110OpenAlexW2109300296MaRDI QIDQ1101027

Thomas Andreae

Publication date: 1986

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

Full work available at URL: https://doi.org/10.1016/0095-8956(86)90026-2

zbMATH Keywords

games on graphscatch a robber

Mathematics Subject Classification ID

2-person games (91A05) Graph theory (05C99) Positional games (pursuit and evasion, etc.) (91A24)

Related Items

Variations on cops and robbers ⋮ On a pursuit game on Cayley graphs ⋮ Cops and robbers in graphs with large girth and Cayley graphs ⋮ Fast Robber in Planar Graphs ⋮ On Meyniel's conjecture of the cop number ⋮ Metric Embedding via Shortest Path Decompositions ⋮ Simplicial decompositions of graphs: A survey of applications ⋮ Helicopter search problems, bandwidth and pathwidth ⋮ Game of cops and robbers in oriented quotients of the integer grid ⋮ On the cop number of graphs of high girth ⋮ A tight lower bound for the capture time of the cops and robbers game ⋮ Cops and Robbers on \(\boldsymbol{P_5}\)-Free Graphs ⋮ To satisfy impatient web surfers is hard ⋮ The one-cop-moves game on graphs with some special structures ⋮ A note on the cops and robber game on graphs embedded in non-orientable surfaces ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ Guard games on graphs: keep the intruder out! ⋮ An annotated bibliography on guaranteed graph searching ⋮ \(k\)-chordal graphs: from cops and robber to compact routing via treewidth ⋮ Cops and robbers on \(2K_2\)-free graphs ⋮ The complexity of pursuit on a graph ⋮ On the cop number of toroidal graphs ⋮ On the generalised colouring numbers of graphs that exclude a fixed minor ⋮ An extension of a fixed point problem for simple graphs ⋮ Pursuing a fast robber on a graph ⋮ A survey on the relationship between the game of cops and robbers and other game representations ⋮ 4-cop-win graphs have at least 19 vertices ⋮ Guarding a subgraph as a tool in pursuit-evasion games ⋮ On a game of policemen and robber ⋮ Cops, Robbers, and Threatening Skeletons: Padded Decomposition for Minor-Free Graphs ⋮ A two-person game on graphs where each player tries to encircle his opponent's men ⋮ A game of cops and robbers played on products of graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A game of cops and robbers
• Note on a pursuit game played on graphs
• Some remarks on interval graphs
• A short note about pursuit games played on a graph with a given genus
• Some results about pursuit games on metric spaces obtained through graph theory techniques
• Vertex-to-vertex pursuit in a graph
• The complexity of searching a graph
• Fixed-edge theorem for graphs with loops