The cop-number conjecture for graphs without long holes

About 7 years old · traced to

Let GG be a graph without a hole of length at least tt, where t≥6t\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 t−4t-4 cops.

The preceding argument gives the bound t−3t-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.

References

Primary source

Vaidy Sivaraman, “Cop number of graphs without long holes”, arXiv:2001.00477 (2019).

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.