Blind cop-width and balanced minors of graphs
Preprint
Abstract
We investigate a pursuit-evasion game on an undirected graph in which a robber, moving at a fixed constant speed, attempts to evade a team of cops who are blind to the robber's location and can quickly travel between any pair of vertices in the graph. The blind cop-width is the minimum number of cops needed to catch the robber on a given graph. We link it with other known graph parameters defined in terms of pursuit-evasion games, and show a new lower bound with respect to treewidth. The proof introduces the notion of balanced minors, where all branch sets of a minor model have equal size.Keywords
All Related Versions
This publication has 12 references indexed in Scilit:
- Further results on the Hunters and Rabbit game through monotonicityInformation and Computation, 2025
- Towards tight(er) bounds for the Excluded Grid TheoremJournal of Combinatorial Theory, Series B, 2021
- Hunting rabbits on the hypercubeDiscrete Mathematics, 2019
- The complexity of zero-visibility cops and robberTheoretical Computer Science, 2015
- Linear layouts measuring neighbourhoods in graphsDiscrete Mathematics, 2006
- Quickly Excluding a Planar GraphJournal of Combinatorial Theory, Series B, 1994
- The Vertex Separation and Search Number of a GraphInformation and Computation, 1994
- Graph Searching and a Min-Max Theorem for Tree-WidthJournal of Combinatorial Theory, Series B, 1993
- The vertex separation number of a graph equals its path-widthInformation Processing Letters, 1992
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986