Cops and Robbers on Graphs without Long or Short Holes
In 2019, Sivaraman conjectured that every $P_k$-free graph has cop number at most $k-3$ for $k\geq 5$. Chudnovsky, Norin, Seymour, and Turcotte proved $P_5$-free graphs have cop number at most $2$. For $k\geq 6$ Sivaraman's conjecture remains widely open. There is little evidence to believe Sivaraman's conjecture is optimal, making the discovery of substantially better bounds interesting, even for subclasses of $P_k$-free graphs. We consider this problem for graphs with no long holes, which generalizes $P_k$-free graphs, that also have some forbidden shorter holes. Specifically, we show that…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.36290
curl -X POST /api/v1/records/arxiv/2610.36290/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.36290/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'