REVIEW 5 major objections 6 minor 1 cited by
$4K_1$-free graph with the cop number $3$
T0 review · 5 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read A 16-vertex graph may refute a long-standing cops-and-robbers conjecture
desk verdict The paper's central counterexample is unsupported: Lemma 3 contradicts the paper's own claim that Shrikhande neighborhoods induce C6, and the proof conflates the graph with its complement. 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 central object is the Shrikhande graph $H$, the 16-vertex graph on $\mathbb{Z}_4\times\mathbb{Z}_4$ whose edges join pairs differing by one of six specified vectors; its complement $\overline H$ is the proposed counterexample. The proof is carried by a strong regularity-type identity, Lemma 2: every two distinct vertices of $H$ have exactly two common neighbors. That identity is used in two ways: it forces $H$ to be $K_4$-free, so $\overline H$ is $4K_1$-free, and it gives the robber in $\overline H$ an escape vertex nonadjacent to both cops at every round, establishing the lower bound $c(\overline H) \ge 3$. For the threshold-degree results, the engine is a known theorem on graphs with a vertex of degree at least $n-6$, which says the graph is $2$-cop-win unless the vertices away from that vertex induce a $C_5$; the paper refines that exceptional case through a partition of the neighborhood into classes $A,B,C,L,X,Y,Z,T$.
What would settle it
Check the vertex and edge sets displayed in Lemma 3 to confirm that they indeed induce a $C_6$ and a $P_6$ in the Shrikhande graph, or run an exhaustive search for induced cycles of length at least 6 in the 16-vertex complement of the Shrikhande graph; finding one would falsify Theorem 2 and the counterexample to the conjecture.
Extended reading notes
Core claim
The paper's central discovery is Theorem 2: $\overline{H}$, the complement of the Shrikhande graph $H$, is $(4K_1, C_\ell)$-free for all $\ell \ge 6$ and has cop number $3$. Since $\overline H$ is $4K_1$-free, the domination-number bound gives $c(\overline H) \le 3$, while the paper argues that two cops cannot force a capture because, at every round, the robber can move to a vertex outside both closed neighborhoods. The argument uses the fact, proved as Lemma 2, that every two distinct vertices of the Shrikhande graph have exactly two common neighbors. From this one graph the paper derives $c(\mathrm{Forb}(4K_1)) = 3$, a counterexample to the conjecture posed in [14], and a negative answer to the question in [16] for $p=4$. The remaining main results are degree-cutoff statements for the class $\mathrm{Forb}(4K_1)$ — $ut(\mathrm{Forb}(4K_1)) = 6$ and $lt(\mathrm{Forb}(4K_1)) \ge 3$ — and the bounds for $(pK_1+qK_2)$-free graphs.
Load-bearing premise
The load-bearing premise is Lemma 3, the claim that the Shrikhande graph has no induced cycle of length at least 6; the proof of that lemma depends on the vertex and edge sets it displays for an induced $C_6$ and $P_6$, and those displayed sets must genuinely be cycles and paths for the counterexample to stand.
Editorial extensions
If this is right
- The class $\mathrm{Forb}(4K_1)$ has cop number exactly $3$, so the proposed bound $c(\mathrm{Forb}(pK_1)) \le p-2$ is false at $p=4$.
- The conjecture that every graph with no induced cycle of length at least $6$ is $2$-cop-win would be false.
- For every $p \ge 2$, $c(\mathrm{Forb}(pK_1+K_2)) \le p+1$, answering the question raised in [16] affirmatively, and for $p,q \ge 2$, $c(\mathrm{Forb}(pK_1+qK_2)) \le p+2q-2$.
- The computational search in the paper indicates that no $4K_1$-free graph on 12 vertices has cop number $3$, so the minimal counterexample, if it exists, has between 13 and 16 vertices.
- Using the upper threshold degree $ut(\mathrm{Forb}(4K_1)) = 6$ and the lower threshold degree at least $3$ reduces the enumeration needed to compute the cop number over this class.
Reading between the lines
- The evasion argument in Theorem 2 uses the two-common-neighbors property more heavily than the full Shrikhande structure, so other strongly regular graphs with similar parameters might yield smaller counterexamples and so directly address the paper's open Question 1.
- The threshold-degree recipe is general: for any hereditary graph class with finite cop number, proving an upper degree cutoff and a lower degree cutoff can reduce cop-number computation to a small bounded-degree residual class, which could be applied to $pK_1$-free classes for $p \ge 5$ where the question remains open.
- If the 16-vertex example is not minimal, the failure of the long-hole conjecture would not be an isolated phenomenon; exhaustive enumeration on 13, 14, and 15 vertices would settle the minimal order.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the cop number of hereditary graph classes defined by forbidding independent sets and matching-like subgraphs. Its main claim (Theorem 2) is that the complement of the 16-vertex Shrikhande graph is (4K1, Cℓ)-free for every ℓ ≥ 6 and has cop number 3; if correct, this would refute Sivaraman's conjecture that every graph without induced cycles of length at least 6 has cop number at most 2, and it would imply c(Forb(4K1)) = 3 (Corollary 1). The paper also defines upper and lower threshold degrees ut(G) and lt(G), proves ut(Forb(4K1)) = 6 and lt(Forb(4K1)) ≥ 3 (Theorems 3–4), reports a computational search over 12-vertex graphs (Section 5), and proves bounds c(Forb(pK1+K2)) ≤ p+1 and c(Forb(pK1+qK2)) ≤ p+2q−2 (Theorems 8–9). The proof of Theorem 2, however, is invalid at several independent points: Lemma 3 is false as stated, the passage from Cℓ-freeness of H to Cℓ-freeness of its complement is logically invalid, and the two-cop lower-bound argument uses adjacency in the wrong graph; consequently the main results of Sections 3–5 that rely on Theorem 2 are unsupported.
Significance. The intended result is significant: a 16-vertex 4K1-free graph with cop number 3 would settle c(Forb(4K1)) and would be the first counterexample to Sivaraman's conjecture, and a positive answer to Turcotte's question on Forb(pK1+K2) would be a useful addition. The paper has strengths worth naming: the upper bound c(H̅) ≤ 3 via domination number is correct in outline, the linked SageMath code supports the Section 5 verification, and the threshold-degree framework is a sensible way to reduce the search space for hereditary classes. These strengths are conditional, however: Theorems 3–4 and the computational filtering inherit the unsupported claim c(H̅) = 3 from Theorem 2, and the proof of the central theorem cannot be checked as written. If the missing arguments were supplied, the paper would be of clear interest to the discrete mathematics community.
major comments (5)
- [§2, Lemma 3 and Claim 3.1] Lemma 3 is false as stated and its proof is invalid. In Claim 3.1 the alleged induced C6 is assigned the nine-edge set {v1v2, v1v4, v1v5, v2v3, v2v5, v3v4, v3v5, v4v6, v5v6}; a 6-cycle on six vertices has exactly six edges, and this set is not a cycle at all, since it contains the 4-cycle v1-v2-v3-v4-v1 and the triangle v1-v2-v5-v1. The subsequent 'induced P6' in the ℓ ≥ 7 part has ten edges and contains a triangle, so it is not a path. Furthermore, the lemma contradicts the paper's own observation, stated just before Lemma 1, that for every vertex u of H the subgraph induced by N(u) is a C6; that neighborhood is itself an induced C6 of H. Hence H does contain an induced C6, and the sentence 'H is Cℓ-free, for all ℓ ≥ 6' cannot be true. The proof of Lemma 3 therefore supplies no support for the Cℓ-freeness claim.
- [§2, proof of Theorem 2] Even if Lemma 3 were true, it would not imply the theorem's conclusion. An induced Cℓ in the complement H̅ corresponds to a set of ℓ vertices whose induced subgraph in H is the complement of Cℓ (for ℓ = 6, the triangular prism), not an induced cycle of H. The proof of Theorem 2 moves from 'By Lemma 3, H is Cℓ-free, ℓ ≥ 6' directly to the claim that the complement is (4K1, Cℓ)-free, and this inference is invalid. The (4K1, Cℓ)-freeness of the complement for all ℓ ≥ 6, which is the property needed to refute Sivaraman's conjecture, is therefore unsupported by the argument given.
- [§2, Theorem 2 lower-bound argument] The two-cop lower-bound proof is run with adjacency in H while the game is played on H̅. In Case 1 (ui = vi) the robber is instructed to choose p with pui ∉ E(H), which is the opposite of the invariant uipi(R) ∉ E(H̅) stated at the end of the proof, and the identity |V(H) \ NH[ui]| = |NH(ui)| = 6 is false: |V(H) \ NH[ui]| = 16 − 7 = 9, while the number of vertices non-adjacent to the cop in H̅ is 16 − 10 = 6. In Case 2 the robber's move is required to satisfy w pi−1(R) ∈ E(H), the opposite of a legal move in H̅, and the contradiction 'NH(ai) ∩ NH(bi) = {ui, vi, pi−1(R)}' is asserted from reversed adjacency assumptions. The claimed bound c(H̅) ≥ 3 is therefore not established; only c(H̅) ≤ γ(H̅) ≤ 3 follows from the text.
- [§6, Theorem 8] The induction step of Theorem 8 invokes two vertices u and v in distinct partite sets of G[A′] and claims that A ∪ {u, v} is a dominating set. When G[A′] has no edges (a complete multipartite graph with a single partite set), such a pair does not exist and A ∪ {u, v} is not dominating, and no alternative dominating set of size p + 1 is produced. This case is not excluded by the hypothesis: a graph consisting of an independent set A of size p − 1, two further pairwise nonadjacent vertices anticomplete to A, and a vertex adjacent to all of A and to one of those two vertices is pK1 + K2-free with G[A′] edgeless. The proof of c(Forb(pK1 + K2)) ≤ p + 1 is therefore incomplete as written.
- [§4, Theorem 4] The proof of Theorem 4 states that Lemmas 8 and 10 imply that every connected 4K1-free graph G with c(G) = 3 has minimum degree at least 3. This does not follow as written: if u has degree 2, the contrapositive of Lemma 10 gives only c(G \ {u}) ≥ 3, and since c(G \ {u}) ≤ 3 by Observation 1 (with connectedness supplied by Lemma 9), G \ {u} is again a 4K1-free graph with cop number 3, which is not a contradiction unless one first selects a minimum-order such graph and reasons inductively; the proof states neither the minimality assumption nor the bound c(G \ {u}) ≤ 3. The theorem's conclusion needs an additional argument.
minor comments (6)
- [§2, opening of Section 2] The sentence 'for the completeness of our result, we will prove that H is (K4, Cℓ)-free, for all ℓ ≥ 6' sits immediately after the statement that every neighborhood N(u) of H induces a C6; the paper should reconcile these two statements, since as written they contradict each other.
- [§2, end of proof of Theorem 2] The inequality γ(H̅) ≤ 3 is asserted without argument; it follows from 4K1-freeness via the standard fact that every maximal independent set is a dominating set, and this should be stated. The proof also switches repeatedly between H and H̅ notation, which makes it very hard to check which graph a given condition refers to.
- [§7, Question 2; §5] The statement in Section 7 that a 4K1-free graph with cop number 3 has at least 13 vertices combines Theorem 4 with the computational verification in Section 5; Section 5 itself only states 'at least 12', so the dependency should be made explicit. Also, 'there does not exist any 4K1 graph having 12 vertices' in Section 5 should read '4K1-free graph'.
- [§1.2 and §3, definitions of ut and lt] The definitions of ut(G) and lt(G) are imprecise: the displayed formula for lt(G) is garbled ('... and G ≠ G′ for all G′ ∈ G′'), and the definition of ut(G) should state explicitly that the witnessing graph with Δ(G′) = |V(G′)| − k − 1 is required to satisfy c(G′) = c(G).
- [§3, Lemma 6] The proof of Lemma 6 contains notation slips (e.g., Claim 6.2's second alternative repeats N(v3) instead of N(v4), and in Claim 6.4 the case p3(R) ∈ X4 is handled after X4 = ∅ was assumed), which make the case analysis hard to audit.
- [§2, Figure 3] Figure 3(a) and (b) are labeled C6 and P6, but the edge sets printed in the proof of Claim 3.1 have nine and ten edges respectively; the figure captions or the text should be corrected to agree with each other.
Circularity Check
No significant circularity: the paper's derivation is self-contained and does not reduce to its inputs by construction.
full rationale
The central claim (Theorem 2) is derived from the fixed, externally defined Shrikhande graph, a direct two-cop lower-bound strategy for the robber, and Observation 1 for the upper bound; Lemma 3 is an attempted independent structural proof, not a restatement of the conclusion. Section 3 uses Baird et al.'s Theorem 5 and the already-proved Theorem 2; Sections 4 and 6 use external theorems of Turcotte plus induction. No parameter is fitted to data, no quantity is defined in terms of the target result, and no load-bearing premise is justified only by a self-citation. The only self-citation, reference [5] by the third author, appears merely in the introductory literature list and carries no argumentative weight. The mathematical concern raised by the skeptical reader—that Lemma 3's proof lists edge sets that are not induced cycles or paths—is a correctness risk rather than circularity, because the lemma's conclusion is not being assumed as an input anywhere in the derivation. Accordingly the circularity score is 0.
Assumptions & free parameters
assumptions (7)
- standard math Shrikhande graph H is the Cayley graph on Z4×Z4 with connection set {(±1,0),(0,±1),(1,1),(−1,−1)}
- domain assumption Baird et al. Theorem 5: every n-vertex graph with a vertex of degree at least n−6 has c(G) ≤ 2 unless the remaining graph is a C5
- domain assumption Chudnovsky et al. Theorem 1: c(Forb(P5)) = 2
- domain assumption Turcotte Theorem 6: c(Forb(2K1+K2)) ≤ 3
- domain assumption Turcotte Theorem 7: c(Forb(qK2)) ≤ 2q−2
- domain assumption Turcotte and Yvon: every 3-cop-win graph on 11 vertices contains a 4K1
- standard math Every K1+K2-free graph is complete multipartite
Cite this review
Pith. "Pith review of $4K_1$-free graph with the cop number $3$." pith.science (2026). https://pith.science/paper/IDC3HO43
@misc{pith2026250515416,
author = {Pith},
title = {Pith review of: $4K_1$-free graph with the cop number $3$},
year = {2026},
howpublished = {\url{https://pith.science/paper/IDC3HO43}},
note = {Machine review of arXiv:2505.15416}
}
abstract
The game of cops and robber is a two-player turn-based game played on a graph where the cops try to capture the robber. The cop number of a graph $G$, denoted by $c(G)$ is the minimum number of cops required to capture the robber. For a given class of graphs ${\cal F}$, let $c({\cal F}):=\sup\{c(F)|F\in {\cal F}\}$, and let Forb$({\cal F})$ denote the class of ${\cal F}$-free graphs. We show that the complement of the Shrikhande graph is $(4K_1,C_{\ell}$)-free for any $\ell \geq 6$ and has the cop number~$3$. This provides a counterexample for the conjecture proposed by Sivaraman (arxiv, 2019) which states that if $G$ is $C_{\ell}$-free for all $\ell\ge 6$, then $c(G)\le 2$. This also gives a negative answer to the question posed by Turcotte (Discrete Math. 345:112660 (2022)) 112660. to check whether $c($Forb$(pK_1))=p-2$. Turcotte also posed the question to check whether $c($Forb$(pK_1+K_2))\leq p+1$, for $p\geq 3$. We prove that this result indeed holds. We also generalize this result for Forb$(pK_1+qK_2)$. Motivated by the results of Baird et al. (Contrib. Discrete Math. 9:70--84 (2014)) and Turcotte and Yvon (Discrete Appl. Math. 301:74--98 (2021)), we define the upper threshold degree and lower threshold degree for a particular class of graphs and show some computational advantage to find the cop number using these.
Figures
Forward citations
Cited by 1 Pith paper
-
Cops and Robbers, Clique Covers, and Induced Cycles
For every k there is a graph whose cop number, independence number, and clique-cover number are all equal to k, and any graph with these equal for k≥3 contains induced cycles of every length from 3 to k+1.
Reference graph
Works this paper leans on
- [1]
- [2]
-
[3]
M. Chudnovsky, S. Norin, P. D. Seymour, J. Turcotte, Cops and robbers on P5-free graphs, SIAM J. Discrete Math. 38 (2024) 845–856
work page 2024
-
[4]
S. Das, H. Gahlawat, On the cop number of string graphs, in 33rd International Symposium on Algorithms and Computation (LIPIcs) 248 (2022) 45:1–45:18
work page 2022
-
[5]
U. K. Gupta, S. Mishra, D. Pradhan, Cops and robber on subc lasses of P5-free graphs, Discrete Math. 346 (2023) 113353
work page 2023
- [6]
-
[7]
The Cop Number of Graphs with Forbidden Induced Subgraphs
M. Liu, The cop number of graphs with forbidden induced su bgraphs, (2019) arXiv:1908.11478v1
work page Pith review arXiv 2019
-
[8]
B. D. McKay, A. Piperno, Practical Graph Isomorphism, II , J. Symbolic Computation 60 (2014) 94–112
work page 2014
Show all 16 references
-
[9]
Nowakowski, P
R. Nowakowski, P. Winkler, Vertex to vertex pursuit in a g raph, Discrete Math. 43 (1983) 235–239
1983
-
[10]
Peeters, Strongly Regular Graphs that are Locally a D isjoint Union of Hexagons, Europ
R. Peeters, Strongly Regular Graphs that are Locally a D isjoint Union of Hexagons, Europ. J. Combinatorics 18 (1997) 579–588
1997
-
[11]
J. Petr, J. Portier, L. Versteegen, A note on cops and rob bers, independence number, domination number and diameter, Discrete Math. 346 (2023) 113175
2023
-
[12]
Quilliot, Jeux et points fixes sur les graphes, Th` ese de 3` eme cycle, Universit´ e de Paris VI, 1978
A. Quilliot, Jeux et points fixes sur les graphes, Th` ese de 3` eme cycle, Universit´ e de Paris VI, 1978
1978
-
[13]
Sivaraman, An application of the Gy´ arf´ as path argument, Discrete Math
V. Sivaraman, An application of the Gy´ arf´ as path argument, Discrete Math. 342 (2019) 2306– 2307
2019
-
[14]
Sivaraman, Cop number of graphs without long holes, ( 2019) arXiv:2001.00477
V. Sivaraman, Cop number of graphs without long holes, ( 2019) arXiv:2001.00477. 20
2019 arXiv
-
[15]
Turcotte, S
J. Turcotte, S. Yvon, 4-cop-win graphs have at least 19 v ertices, Discrete Appl. Math. 301 (2021) 74–98
2021
-
[16]
Turcotte, Cops and robber on 2 K2-free graphs, Discrete Math
J. Turcotte, Cops and robber on 2 K2-free graphs, Discrete Math. 345 (2022) 112660. 21
2022
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.