2025/09/13 by Alexander Clow, Clow, Alexander, Erin Kathleen McKenna Meger +1
Computer Science · Decision Sciences · #05C57 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Game Theory and Applications #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.2509.10941
openalex publication_date 2025/09/13 · openalex created_date 2025/10/12 · openalex updated_date 2026/07/28
In 2019, Sivaraman conjectured that every Pk-free graph has cop number at most k-3. In the same year, Liu proved this conjecture for (Pk,claw)-free graphs. Recently Chudnovsky, Norin, Seymour, and Turcotte proved this conjecture for P5-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 (Pk,E)-free graphs have cop number at most \lceil (k-1)/(2) \rceil +3, which improves and generalizes Liu's result for (Pk,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 (2p)/(3) \rceil+3. This improves a bound of Joret, Kamiński, and Theis. Our proof relies on demonstrating that all (Pk,claw,butterfly,C4,C5)-free graphs have cop number at most \lceil(k-1)/(3)\rceil +3.