Cop number of -free graphs without a claw or a fork
In the authors' words
In 2019, Liu proved that the cop number of any -free graph is at most . In 2026, Clow and Meger improved and generalized the result of Liu by showing that every connected -free graph has cop number at most , where the graph is obtained by subdividing two edges of a claw. In this paper, we show that every -free graph has cop number at most . This improves the result of Clow and Meger on claw-free graphs. We further show that this bound can be improved to , when contains a hole of length at least . We show that the cop number of any -free graph is at most . This also improves the result of Clow and Meger on fork-free graphs for some values of . We further show that every -free graph has cop number at most , and this bound is tight.
Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.
Authors' comment: 11 pages, 2 figures, 1 table