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

From papers

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 k1k\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

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

Solutions 0

No solutions have been posted yet.