Tootfinder

Cops and Robbers on Graphs with Path Constraints
Alexander Clow, Erin Meger
https://arxiv.org/abs/2509.10941 https://arxiv.org/pdf/2509.10941

Cops and Robbers on Graphs with Path Constraints
In 2019, Sivaraman conjectured that every $P_k$-free graph has cop number at most $k-3$. In the same year, Liu proved this conjecture for $(P_k,\text{claw})$-free graphs. Recently Chudnovsky, Norin, Seymour, and Turcotte proved this conjecture for $P_5$-free graphs. For $k\geq 6$ the conjecture remains widely opened. Let the $E$ graph be the $\text{claw}$ with two subdivided edges. We show that all $(P_k,E)$-free graphs have cop number at most $\lceil \frac{k-1}{2} \rceil +3$, which improves an…