← All problems

Sivaraman's cop-number conjecture for path-free graphs

7 years old · traced to

Let PkP_k denote the path on kk vertices, let GG be a graph, and let c(G)c(G) denote its cop number. A graph is PkP_k-free if it contains no induced subgraph isomorphic to PkP_k. Sivaraman's conjecture. For all k≥5k\geq 5, if GG is PkP_k-free, then

c(G)≤k−3.c(G)\leq k-3.

The conjecture proposes an improvement over the known bound that every connected PkP_k-free graph is (k−2)(k-2)-cop win. Its general P5P_5 case was recently proved by Chudnovsky, Norin, Seymour, and Turcotte; the statement for general kk is therefore not uniformly open in the same form.

References

9 papers in this index state this conjecture (2019–2025). The statement above is taken from the most recent of them; the others are arXiv:2505.15416, arXiv:2504.04496, arXiv:2504.14863, arXiv:2302.06800, arXiv:2104.02807, arXiv:2001.03124, arXiv:1908.11478, arXiv:1903.11484.

Source: Alexander Clow and Erin Meger, “Cops and Robbers on Graphs with Path Constraints”, arXiv:2509.10941 (2025).

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.