The two 1-visibility cops cleaning conjecture

Let GG be a connected graph. Two 1-visibility cops are cops whose visibility parameter is 11, 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 1010 vertices of GG, or they can clean the whole graph.

This conjecture proposes that 1010 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 1010 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.