Conjecture on the cop number of graphs forbidding an induced cycle

From papers

For an integer 3\ell\geq 3, let CC_\ell be the cycle with \ell vertices. A graph GG is CC_\ell-free if it contains no induced subgraph isomorphic to CC_\ell; write c(G)c(G) for its cop number and α(G)\alpha(G) for its independence number. Induced-cycle-free cop-number conjecture. For every integer 3\ell\geq 3, almost every CC_\ell-free graph GG satisfies

c(G)<α(G).c(G)<\alpha(G).

This extends the paper's motivation from the case of C4C_4-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

No solutions have been posted yet.