The cop-number conjecture for connected -free graphs
The cop-number conjecture for connected -free graphs
Let ) be a connected graph with no induced path , where . In the cops-and-robber game on , 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 cops.
The conjecture asks whether the theorem proved in the paper, that cops capture the robber in at most moves, can be strengthened by one fewer cop for connected -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.