Conjecture on the cop number of graphs forbidding an induced cycle
Conjecture on the cop number of graphs forbidding an induced cycle
For an integer , let be the cycle with vertices. A graph is -free if it contains no induced subgraph isomorphic to ; write for its cop number and for its independence number. Induced-cycle-free cop-number conjecture. For every integer , almost every -free graph satisfies
This extends the paper's motivation from the case of -free graphs, for which the asserted inequality is proved for almost every graph, to all forbidden induced cycles. The source presents the statement as a conjecture and gives no resolution.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary source
Alexander Clow and Imed Zaguia, “Cops and Robbers, Clique Covers, and Induced Cycles”, arXiv:2507.14321 (2025).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.