REVIEW 3 major objections 5 minor 17 references
Cops and Robbers, Clique Covers, and Induced Cycles
T0 review · 3 major / 5 minor · reviewed 2026-08-06 · deepseek-v4-flash
Pith's one-line read Random graphs show that for every k there is a graph whose cop number, independence number, and clique cover number are all k, and any such connected graph with k≥3 contains induced cycles of every length up to k+1.
desk verdict Solid, publishable-after-minor-fixes paper: strong existence theorem plus a clean structural consequence, with two fixable proof slips in the details. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The random graph model $H(k,\ell,p)$ is the engine of the existence half. It consists of $k$ equal-sized cliques with cross-edges chosen independently at probability $p=2k\log(\ell)/\ell$, and its load-bearing property is the Lemma 2.4 "no-cover" condition: for every vertex $v$ and every other clique $S_j$, the set $N(v)\cap S_j$ is not contained in the union of the closed neighbourhoods of any $k-1$ vertices. That condition is exactly what lets a robber evade $k-1$ cops by moving to a neighbour in an unoccupied clique. For the structural half, the clique cover $K^{(1)},\dots,K^{(k)}$ of $G$ is the object. Lemma 3.2 shows that a robber with a winning strategy must sit in the final clique and be adjacent to every other clique of the cover, and the cop strategy built from that lemma forces the robber's successive positions $u_1,\dots,u_k$ to induce a path, with the last escape move creating an induced $C_{k+1}$.
What would settle it
A direct search for a connected graph with $c(G)=\theta(G)=5$ that contains no induced cycle of length 5 would disprove Theorem 1.2; such a search can be run exhaustively on graphs up to a modest number of vertices.
Extended reading notes
Core claim
The central claim is Theorem 1.1: for every fixed $k\ge1$ there exists a graph $G$ with at most $11\log(k)2^{k^4}$ vertices and $c(G)=\theta(G)=k$; since $c\le\alpha\le\theta$, this gives $c(G)=\alpha(G)=\theta(G)=k$. The graph is constructed as $H(k,\ell,p)$: $k$ disjoint cliques $S_1,\dots,S_k$, each of size $\ell$, with each edge between different cliques present independently with probability $p=2k\log(\ell)/\ell$. A maximum-degree estimate forces $\theta(H)=k$, while a separate adjacency estimate guarantees that, for every vertex $v$ and every other clique $S_j$, the neighbourhood $N(v)\cap S_j$ cannot be covered by the closed neighbourhoods of any $k-1$ other vertices. When all these events hold simultaneously, a single robber can answer any move of $k-1$ cops by stepping to an uncovered vertex, so $c(G)=k$. The paper's second main theorem is structural: if $G$ is connected and $c(G)=\theta(G)=k\ge3$, then $G$ contains an induced cycle of every length $t$ with $3\le t\le k+1$. The proof makes $k-1$ cops herd the robber along vertices $u_1,\dots,u_k$ that induce a path, and the final forced robber move closes an induced cycle of length $k+1$.
Load-bearing premise
The existence proof of Theorem 1.1 rests on the assertion that the three numerical inequalities in Section 2 are simultaneously satisfiable for every $k\ge3$ when $\ell=11\log(k)2^{k^3}$; the paper provides this as a verification rather than a written derivation, and if the assertion failed for some $k$ the probabilistic construction would not produce a graph.
Editorial extensions
If this is right
- For every $k\ge1$ there are infinitely many graphs with $c(G)=\alpha(G)=\theta(G)=k$, not just one example per $k$.
- The 2022 question is answered in the negative: the bound $c(G)\le\alpha(G)$ is tight for every value of $\alpha$, not only for $\alpha=3$.
- Connected perfect graphs with $\alpha(G)\ge4$ always satisfy $c(G)<\alpha(G)$, so equality between cop number and independence number is a non-perfect phenomenon in that range.
- Every connected graph with $c(G)=\theta(G)=k\ge3$ contains a triangle and an induced cycle of every length through $k+1$, so such graphs cannot be bipartite or chordal, and for $k\ge4$ they cannot be perfect.
- If almost all $3K_1$-free and $2K_2$-free graphs satisfy $\chi=\omega$, then almost every triangle-free graph and almost every $C_4$-free graph satisfies $c(G)<\alpha(G)$.
Reading between the lines
- The vertex bound $11\log(k)2^{k^4}$ is a crude existence certificate, and the paper leaves open how small the smallest graph with $c(G)=\theta(G)=k$ can be; the true growth rate may be far below $2^{k^4}$.
- The induced-cycle theorem suggests that $c(G)=\theta(G)$ puts a graph at the opposite extreme from perfect graphs; families defined by forbidding odd holes and antiholes are plausible candidates where $c<\alpha$ should hold once $\alpha$ is large.
- If the cited $\chi=\omega$ statement for almost all $H$-free graphs is later proved for every forest $H$, the argument of Section 4 should extend to a much wider family of forbidden-induced-subgraph classes than just triangle-free and $C_4$-free graphs.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the Cops and Robbers game and the parameters c(G) ≤ α(G) ≤ θ(G). Its main results are Theorem 1.1, a random-graph construction giving, for every k ≥ 1, a graph G with at most 11 log(k) 2^{k^4} vertices and c(G) = θ(G) = k; and Theorem 1.2, a structural statement that any connected graph with c(G) = θ(G) = k ≥ 3 contains induced cycles of every length 3 ≤ t ≤ k + 1. Theorem 1.3 then follows: no connected perfect graph with α(G) ≥ 4 can have c(G) = α(G). Section 4 gives a conditional result that, assuming almost all 3K1-free and 2K2-free graphs have χ = ω, almost every triangle-free or C4-free graph satisfies c(G) < α(G). The probabilistic lower bound for the cop number rests on a robber-evasion strategy using a 'no-cover' event for neighbourhoods, while the structural argument uses clique covers and an induction on the number of cliques.
Significance. If the proofs are repaired, the paper settles Turcotte's question in the strongest natural sense: the inequality c(G) ≤ α(G) is tight for every value of the independence number, not only α = 3. The structural theorem is elegant and the perfect-graph corollary is a nice application of the Strong Perfect Graph Theorem. The random construction is conceptually transparent and the robber strategy is a standard and convincing use of a non-dominating-set / no-cover argument. The paper also makes a reasonable conditional contribution for typical triangle-free and C4-free graphs. The main ideas appear sound, but several technical points in the written proofs need correction or elaboration before the results are established as stated.
major comments (3)
- [Section 2, Lemma 2.4] The displayed inequality for P(E_{v,j} | X = x) P(X = x) has the wrong exponent of ℓ. Multiplying the two displayed bounds gives a factor ℓ^{x(2k/ℓ − 1)} (after extracting ℓ^{−2k}), not ℓ^{x(1/ℓ − 1)}. Consequently the exponential term in the final probability bound should be exp(4k^3 log(ℓ)^2 ℓ^{2k/ℓ − 1}), not exp(4k^3 log(ℓ)^2 ℓ^{1/ℓ − 1}). This bound is the only source of the positive probability in Theorem 1.1, so the proof as written is incorrect at a load-bearing step. The error appears repairable — for the proposed ℓ = 11 log(k)2^{k^3} the corrected term is only negligibly larger — but the lemma must be corrected and re-verified.
- [Section 2, Lemma 2.2 and proof of Theorem 1.1] The condition in Lemma 2.2 is stated as 5k(k−1) log ℓ ≤ ℓ^{k−1}, but the proof's step P(Y ≥ ℓ/(k−1)) ≤ P(Y ≥ 5k(k−1) log ℓ) requires 5k(k−1) log ℓ ≤ ℓ/(k−1), i.e. 5k(k−1)^2 log ℓ ≤ ℓ. The displayed inequality (1) in the proof of Theorem 1.1 repeats the erroneous ℓ^{k−1}. In addition, the assertion that ℓ = 11 log(k)2^{k^3} satisfies inequalities (1)–(3) is stated without any derivation; after the correction to Lemma 2.4 this verification must be supplied explicitly, since the whole positive-probability argument rests on it.
- [Section 3, proof of Theorem 1.2] The induction step applies the induction hypothesis to G′ = G − K(k) as if G′ were a connected graph with c(G′) = θ(G′) = k − 1. Connectivity of G′ is not proved. If G′ is disconnected, then c(G′) = Σ c(C_i) = k − 1 and one obtains c(C_i) = θ(C_i) for each component, but componentwise induction yields induced cycles only up to max θ(C_i) + 1, which is at most k − 1 when there is more than one component; it does not yield an induced C_k in G′. The proof needs either a proof that G′ is connected or an additional argument covering the disconnected case.
minor comments (5)
- [Section 3, Lemma 3.3] In case (3) of the cop-move description, the condition should be N(u′) ∩ K(i) = ∅ rather than N(u) ∩ K(i) = ∅; as written the case distinction refers to the wrong vertex (u is the initial robber vertex in K(k), while u′ is the robber's destination in K(1)).
- [Section 4, proof of Theorem 1.4] The proof treats connected Cℓ-free graphs and then concludes 'almost every' Cℓ-free graph satisfies c(G) < α(G). This step needs a justification that almost all Cℓ-free graphs are connected, or a componentwise argument, since the inequalities c ≤ α ≤ θ are componentwise.
- [Throughout] There are several typographical slips: 'compliment' should be 'complement' in the abstract and Figure 1 caption, 'there exists infinity many graphs' should be 'there exist infinitely many graphs' near the end of Section 2, and 'forces the robber to being' should be 'forces the robber to be' in Lemma 3.4.
- [Section 3, proof of Theorem 1.2] The claim that θ(G′) = k − 1 is stated as 'easily verified' but is not immediate from the clique cover alone; it follows only after combining θ(G′) ≤ k − 1 with the lower bound c(G′) ≥ k − 1 and the general inequality c(G′) ≤ θ(G′). The exposition should say this explicitly.
- [Section 4, Lemma 4.3] The assertion that a singleton clique yields a corner is true but not quite 'trivial'; a one-sentence justification (the singleton vertex has closed neighbourhood contained in that of any adjacent vertex of the other clique) would help the reader.
Circularity Check
No significant circularity: the paper's constructions and structural arguments are self-contained and do not reduce to their inputs.
full rationale
The paper derives its main theorems from first principles. Theorem 1.1 is proved by an explicit random graph construction: the authors define H(k, ℓ, p), prove probabilistic upper bounds on the maximum degree (Lemma 2.2), derive θ(H)=k from that bound (Lemma 2.3), prove a high-probability adjacency property that rules out certain robber-capturing configurations (Lemma 2.4), and then combine these with a direct robber evasion strategy. The evasion strategy uses exactly the stated properties, but this is a construction whose parts are independently established, not a case of assuming the conclusion. The structural results in Section 3 build on lemmas about clique covers and game play, and the induction in Theorem 1.2 is internally coherent; each step is argued rather than assumed. Theorem 1.4 is explicitly conditional on an external conjecture about almost all 3K1-free and 2K2-free graphs having χ=ω, and the paper flags this dependence honestly. There are no self-citations that carry the argument, no fitted parameters relabeled as predictions, and no known result merely renamed. The reviewer's noted algebraic slip in Lemma 2.4 concerns the numerical correctness of a probability bound, not circularity: even if the bound were flawed, that would be an error in the proof, not a logical reduction of the theorem to its own assumption. Therefore the circularity score is 0.
Assumptions & free parameters
free parameters (2)
- ℓ =
11 log(k)2^{k^3}
- p =
2k log(ℓ)/ℓ
assumptions (6)
- standard math c(G) ≤ α(G) ≤ θ(G) for every graph G
- standard math Chernoff bound (Lemma 2.1)
- standard math R(3,3)=6
- standard math Corner vertex removal lemma
- standard math Weak and strong perfect graph theorems
- ad hoc to paper Almost all 3K1-free graphs and 2K2-free graphs have χ=ω
Cite this review
Pith. "Pith review of Cops and Robbers, Clique Covers, and Induced Cycles." pith.science (2026). https://pith.science/paper/JAM4ZO4O
@misc{pith2026250714321,
author = {Pith},
title = {Pith review of: Cops and Robbers, Clique Covers, and Induced Cycles},
year = {2026},
howpublished = {\url{https://pith.science/paper/JAM4ZO4O}},
note = {Machine review of arXiv:2507.14321}
}
abstract
We consider the Cops and Robbers game played on finite simple graphs. In a graph $G$, the number of cops required to capture a robber in the Cops and Robbers game is denoted by $c(G)$. For all graphs $G$, $c(G) \leq \alpha(G) \leq \theta(G)$ where $\alpha(G)$ and $\theta(G)$ are the independence number and clique cover number respectively. In 2022 Turcotte asked if $c(G) < \alpha(G)$ for all graphs with $\alpha(G) \geq 3$. Recently, Char, Maniya, and Pradhan proved this is false, at least when $\alpha = 3$,by demonstrating the compliment of the Shrikhande graph has cop number and independence number $3$. We prove, using random graphs, the stronger result that for all $k\geq 1$ there exists a graph $G$ such that $c(G) = \alpha(G) = \theta(G) = k$. Next, we consider the structure of graphs with $c(G) = \theta(G) \geq 3$. We prove, using structural arguments, that any graphs $G$ which satisfies $c(G) = \theta(G) = k \geq 3$ contain induced cycles of all lengths $3\leq t \leq k+1$. This implies all perfect graphs $G$ with $\alpha(G)\geq 4$ have $c(G) < \alpha(G)$. Additionally,we discuss if typical triangle-free and $C_4$-free graphs will have $c(G) < \alpha(G)$.
Figures
Reference graph
Works this paper leans on
-
[1]
M. Aigner and M. Fromme. A game of Cops and Robbers. Discrete Applied Mathematics , 8(1):1–12, 1984
work page 1984
-
[2]
T. Andreae. On a pursuit game played on graphs for which a minor is excluded.Journal of Combinatorial Theory, Series B , 41(1):37–47, 1986
work page 1986
-
[3]
A. Bonato and R. Nowakowski. The game of Cops and Robbers on graphs . American Mathematical Soc., 2011
work page 2011
-
[4]
A. Char, P. V. Maniya, and D. Pradhan. 4 K1-free graph with the cop number 3. arXiv preprint arXiv:2505.15416, 2025
work page Pith review arXiv 2025
-
[5]
M. Chudnovsky, S. Norin, P. D. Seymour, and J. Turcotte. Cops and Robbers on P5-free graphs. SIAM Journal on Discrete Mathematics , 38(1):845–856, 2024
work page 2024
-
[6]
M. Chudnovsky, N. Robertson, P. Seymour, and R. Thomas. The strong perfect graph theorem. Annals of mathematics , pages 51–229, 2006
work page 2006
- [7]
- [8]
Show all 17 references
-
[9]
Kenter, E
F. Kenter, E. Meger, and J. Turcotte. Improved bounds on the cop number when forbidding a minor. Journal of Graph Theory , 108(3):620–646, 2025
2025
-
[10]
Lov´ asz
L. Lov´ asz. Normal hypergraphs and the perfect graph conjecture. Discrete Mathematics, 2(3):253–267, 1972
1972
-
[11]
Masjoody and L
M. Masjoody and L. Stacho. Cops and Robbers on graphs with a set of forbidden induced subgraphs. Theoretical Computer Science, 839:186–194, 2020
2020
-
[12]
Nowakowski and P
R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph.Discrete Mathematics, 43(2-3):235– 239, 1983
1983
-
[13]
Quilliot
A. Quilliot. Problemes de jeux, de point fixe, de connectivit´ e et de repr´ esentation sur des graphes, des ensembles ordonn´ es et des hypergraphes.These d’Etat, Universit´ e de Paris VI, pages 131–145, 1983
1983
-
[14]
Reed and Y
B. Reed and Y. Yuditsky. The asymptotic χ-boundedness of hereditary families. arXiv preprint arXiv:2506.01070, 2025. 14
2025 arXiv
-
[15]
Sivaraman
V. Sivaraman. An application of the Gy´ arf´ as path argument.Discrete Mathematics, 342(8):2306–2307, 2019
2019
-
[16]
Turcotte
J. Turcotte. Cops and Robbers on 2 K2-free graphs. Discrete Mathematics, 345(1):112660, 2022
2022
-
[17]
D. B. West. Introduction to Graph Theory , volume 2. Prentice hall Upper Saddle River, 2001. Department of Mathematics, Simon Fraser University Email address : alexander clow@sfu.ca Department of Mathematics and Computer Science, Royal Military College of Canada Email address ...
2001
Reviewed August 6, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.