Cop number of $P_k$-free graphs without a claw or a fork
In 2019, Liu proved that the cop number of any $(P_k, claw)$-free graph is at most $k-3$. In 2026, Clow and Meger improved and generalized the result of Liu by showing that every connected $(P_k, E)$-free graph has cop number at most $\lceil \frac{k-1}{2} \rceil + 3$, where the graph $E$ is obtained by subdividing two edges of a claw. In this paper, we show that every $(P_k, claw)$-free graph $G$ has cop number at most $\lceil \frac{k-1}{2} \rceil$. This improves the result of Clow and Meger on claw-free graphs. We further show that this bound can be improved to $\lceil \frac{k}{3}\rceil$,…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.20129
curl -X POST /api/v1/records/arxiv/2610.20129/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.20129/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'