The cop-number conjecture for connected PtP_t-free graphs

Let GG) be a connected graph with no induced path PtP_t, where t5t\geq 5. In the cops-and-robber game on GG, the cops and robber move along edges, and the cops capture the robber by occupying his vertex.

Cop-number conjecture. The robber can be captured by t3t-3 cops.

The conjecture asks whether the theorem proved in the paper, that t2t-2 cops capture the robber in at most t1t-1 moves, can be strengthened by one fewer cop for connected PtP_t-free graphs. Its status is not resolved in the supplied source.

Sources & referencesView supporting material

Primary source

Vaidy Sivaraman, “An application of the Gyárfás path argument”, arXiv:1903.01338 (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.