Linear cop-number conjecture for claw-free path-free graphs

Let PkP_k denote the path on kk vertices, let claw⁡=K1,3\operatorname{claw}=K_{1,3}, and let c(G)c(G) denote the cop number of a graph GG. A graph is (Pk,claw⁡)(P_k,\operatorname{claw})-free if it contains neither an induced PkP_k nor an induced claw. Linear cop-number conjecture. There exists an ε>0\varepsilon>0 such that for every integer k≥1k\geq 1, there is a (Pk,claw⁡)(P_k,\operatorname{claw})-free graph GG with

c(G)≥εk.c(G)\geq \varepsilon k.

This conjecture asks for a linear lower bound on the cop number even after forbidding both a path and a claw. The source notes that existing random PkP_k-free examples with large cop number are typically not claw-free, and presents this as an easier-to-prove alternative to determining the precise asymptotic bound; it remains open.

References

Primary 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.