The cop-number conjecture for graphs without long holes
The cop-number conjecture for graphs without long holes
Let be a graph without a hole of length at least , where . A cop is one player in the cops-and-robber game on , and the cop number is the minimum number of cops needed to capture the robber.
Cop-number conjecture. The graph can be won by cops.
The preceding argument gives the bound cops, so this conjecture proposes improving it by one. Its first case, that two cops suffice for graphs without holes of length at least six, is highlighted as particularly interesting; the source states that the conjecture remains open.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Vaidy Sivaraman, “Cop number of graphs without long holes”, arXiv:2001.00477 (2019).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.