The cop-number conjecture for graphs without long holes

From papers

Let GG be a graph without a hole of length at least tt, where t6t\geq 6. A cop is one player in the cops-and-robber game on GG, and the cop number is the minimum number of cops needed to capture the robber.

Cop-number conjecture. The graph GG can be won by t4t-4 cops.

The preceding argument gives the bound t3t-3 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

No solutions have been posted yet.