pipette
ESEspañol

Cop number of -free graphs without a claw or a fork

Uttam K. Gupta, Dinabandhu Pradhan, and Rashmi Rekha Swain

Preprint

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.

Main resultLimitation the authors admit

Appeared: Thursday, October 15. arXiv. Preprint, not yet peer-reviewed.

Authors' comment: 11 pages, 2 figures, 1 table