The two 1-visibility cops cleaning conjecture
The two 1-visibility cops cleaning conjecture
Let be a connected graph. Two 1-visibility cops are cops whose visibility parameter is , and a graph is cleaned when all its vertices are visited according to the rules of the limited-visibility cops and robbers game.
Two 1-visibility cops cleaning conjecture. Two 1-visibility cops can clean at least vertices of , or they can clean the whole graph.
This conjecture proposes that is the maximum guaranteed number of cleaned vertices for two 1-visibility cops unless the entire connected graph can be cleaned. The paper reports computational evidence for connected graphs up to vertices and notes the Heawood graph as an example that cannot be completely cleaned by two such cops.
Sources & referencesView supporting material
Primary source
Bojan Bašić, Alfie Davies, Aleksa Džuklevski, Strahinja Gvozdić and Yannick Mogge, “Seeing is not believing in limited visibility cops and robbers”, arXiv:2507.00941 (2025).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.