Cops and Robbers on Graphs with Path Constraints

Abstract

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\ge 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 and generalizes Liu's result for $(P_k,\text{claw})$-free graphs. We also prove that if $G$ is a graph whose longest path is length $p$, then $G$ has cop number at most $\lceil \frac{2p}{3}\rceil +3$. This improves a bound of Joret, Kamiński, and Theis. Our proof relies on demonstrating that all $(P_k,\text{claw},\text{butterfly},C_4,C_5)$-free graphs have cop number at most $\lceil \frac{k-1}{3}\rceil +3$.

18 pages, 6 figures