Cops and Robbers on Graphs with Path Constraints

In 2019, Sivaraman conjectured that every Pₖ-free graph has cop number at most $k-3$. In the same year, Liu proved this conjecture for (Pₖ,claw)-free graphs. Recently Chudnovsky, Norin, Seymour, and Turcotte proved this conjecture for P₅-free graphs. For k≥ 6 the conjecture remains widely opened. Let the E graph be the claw with two subdivided edges. We show that all (Pₖ,E)-free graphs have cop number at most k-1/2 +3, which improves and generalizes Liu's result for (Pₖ,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 2p/3 +3. This improves a bound of Joret, Kamiński, and Theis. Our proof relies on demonstrating that all (Pₖ,claw,butterfly,C₄,C₅)-free graphs have cop number at most -1/3 +3.