Blind cop-width and balanced minors of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915642119028736 |
|---|---|
| author | Buffière, Hector Campbell, Rutger Hendrey, Kevin Oum, Sang-il |
| author_facet | Buffière, Hector Campbell, Rutger Hendrey, Kevin Oum, Sang-il |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_22278 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Blind cop-width and balanced minors of graphs Buffière, Hector Campbell, Rutger Hendrey, Kevin Oum, Sang-il Combinatorics 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. |
| title | Blind cop-width and balanced minors of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2511.22278 |