Linear cop-number conjecture for claw-free path-free graphs
Linear cop-number conjecture for claw-free path-free graphs
Let denote the path on vertices, let , and let denote the cop number of a graph . A graph is -free if it contains neither an induced nor an induced claw. Linear cop-number conjecture. There exists an such that for every integer , there is a -free graph with
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 -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
Sign in to submit a solution.
No solutions have been posted yet.