Cop number of -free graphs without a claw or a fork
En palabras de los autores
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.
Apareció: jueves, 15 de octubre. arXiv. Preprint, todavía sin revisión por pares.
Comentario de los autores: 11 pages, 2 figures, 1 table