{"id":"8dcdf775-4b30-4b14-bcf8-788aea918fde","arxiv_id":"2509.10941","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Forbidden-subgraph classes of graphs with no long induced path are shown to have cop number at most about k/2 for (P_k,E)-free graphs and at most ceil(2p/3)+3 when the longest path has p vertices.","lead":"This paper proves new upper bounds on the cop number of graphs that avoid long induced paths and certain claw-like structures, including all (P_k,E)-free graphs. The results improve known bounds for path-constrained graph classes and make progress on a conjecture by Sivaraman about cops and robbers.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 1.5's Step 2 rests on an unproven 'easy corollary': the first time the robber is within distance 2 of a cop, it need not be adjacent to the cops' path, yet the whole E-free strategy depends on that adjacency.","rationale":"The reader's weakest assumption was the imported clique-substitution lemma (Lemma 4.4), which is plausible and is not the place where the central proof most needs scrutiny. The more immediate problem is inside Section 5: Theorem 1.5's Step 2 cannot start unless the robber is adjacent to the path w_0...w_t, and the paper explicitly delegates this to an unproved 'easy corollary' of Step 1. The available invariants only yield a first time with D_t≤2, which is weaker than adjacency to the path. The deletion construction makes off-path common neighbors entirely consistent with the maintained inequalities, so this is a genuine gap rather than a routine detail. The Lemma 5.1 subgraph error strengthens the impression that Section 5 has not been fully checked. The theorem may well be true, and the rest of the paper contains substantial ideas, so a rejection is not warranted; the appropriate outcome is conditional acceptance pending a rigorous derivation of the Step 1-to-Step 2 corollary (and correction of the Lemma 5.1 induced subgraph).","tokens_in":15606,"tokens_out":23105,"duration_ms":190686,"concrete_test":"Test the Step 1-to-Step 2 transition directly: simulate the Step 1 strategy on small (P_k,E)-free graphs with cops on every second path vertex, and search for the first turn t with D_t=2 where N(v_t)∩{w_0,...,w_t}=∅. A concrete witness would be a graph with an induced path w_0...w_t, an off-path vertex x adjacent only to w_1 and v_t, and v_t adjacent only to x and the previous robber vertex v_{t-1}; check whether this configuration is reachable under the stated cop strategy and whether the graph is (P_k,E)-free for k=t+1. If such a witness exists, the claimed corollary is false. If not, provide an explicit proof of the invariant that D_t=2 forces the robber to have a neighbor on the path; the current text does not contain such a proof.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"In the proof of Theorem 1.5 (Section 5), Step 1 ends with the assertion: 'when reaching Step 2, we assume the robber is adjacent to a vertex of the path w_0...w_t, which is an easy corollary of the argument.' This transition is load-bearing: Step 2 immediately requires the robber to be adjacent to some w_q, uses that to place cops on w_{q-1} and w_{q+1}, designates C0 on w_{q+1}, and builds the new path u_1... from there. The Step 1 invariant, however, only guarantees a first turn t with D_t ≤ 2, i.e. some cop is at distance 2 from v_t; it does not guarantee N(v_t) intersects {w_0,...,w_t}. The common neighbor x could lie outside the path, and the deletion rule G_{i+1}=G_i-(N[w_i]\\{w_{i+1}}) explicitly removes such off-path neighbors during the construction. At the first failure time t, the implication that v_t ∈ V(G_t) is no longer available, so an off-path common neighbor is not ruled out by the invariant. If the robber has no neighbor on the path, the pincer setup of Step 2 cannot be started, and the subsequent E-free flail argument does not apply. Since this is the main proof of the paper's headline generalization of Liu's theorem, the missing proof of this 'easy corollary' is the most load-bearing gap. As a separate signal that Section 5 is under-checked, Lemma 5.1's displayed induced subgraph has seven vertices and includes u_k, although E has six vertices; the intended six-vertex set appears to be {u_{i-2},u_{i-1},u_i,u_{i+1},v_j,u_{k+1}}.","agreement_with_reader":"disagree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the cop number of graphs with forbidden induced paths and related structures. In Theorem 1.2 the authors prove that every (P_k, claw, butterfly, C_4, C_5)-free graph has cop number at most ceil((k-1)/3)+3. In Theorem 1.3 they show, via the clique-substitution operation of Joret, Kamiński, and Theis, that a graph with longest path length p and cop number at least t yields a (P_{2p+1}, claw, butterfly, C_4, C_5)-free graph H with c(H) at least t; combining this with Theorem 1.2 gives Theorem 1.4, c(G) ≤ ceil(2p/3)+3 for every graph whose longest path has length p. The final main result, Theorem 1.5, states that every (P_k, E)-free graph has cop number at most ceil((k-1)/2)+3, where E is the claw with two subdivided edges; this generalizes and improves Liu's bound for (P_k, claw)-free graphs. The proofs use Gyárfás-path arguments, several structural lemmas about induced flails, and the clique-substitution construction.","tokens_in":16003,"tokens_out":24800,"duration_ms":189176,"significance":"If the results are correct, the paper makes a substantial contribution: Theorem 1.5 gives a bound about half of Liu's for the larger (P_k, E)-free class, and Theorem 1.4 improves the Joret--Kamiński--Theis bound for graphs with bounded longest path. The arguments are largely self-contained and do not rely on fitted parameters or circular reasoning; the only imported black box is Lemma 4.4 from [9], which is an independent published result. The paper also gives useful context relating these bounds to Sivaraman's conjecture and the weak Meyniel conjecture. The main weakness is an unproved transition in the proof of Theorem 1.5 that the strategy's Step 2 depends on; this needs to be repaired before the headline theorem can be considered fully verified.","major_comments":[{"comment":"The sentence 'when reaching Step 2, we assume the robber is adjacent to a vertex of the path w_0...w_t, which is an easy corollary of the argument' is load-bearing and is not justified in the text. The invariant established in Step 1 only guarantees a first turn t with D_t ≤ 2; it does not by itself show that the robber has a neighbour on the path w_0...w_t. The common vertex realizing distance 2 to a cop could lie off the path, and at the first failure time the robber's vertex need not lie in G_t. Since Step 2 immediately requires the robber to be adjacent to some w_q, uses that to place cops on w_{q-1} and w_{q+1}, and builds the new path from there, the entire E-free 'flail' argument in Step 2 has no starting point without this adjacency. Please supply a proof of this corollary or modify the strategy so that this adjacency is not assumed.","section":"Section 5, proof of Theorem 1.5, Step 1 to Step 2"},{"comment":"The proof of Lemma 5.1 displays the set {u_{i-2}, u_{i-1}, u_i, u_{i+1}, v_j, u_{k+1}, u_k}, which has seven vertices, but E has six vertices. As written, this set does not induce E. The intended six-vertex induced E is almost certainly {u_{i-2}, u_{i-1}, u_i, u_{i+1}, v_j, u_{k+1}}, with center u_i and arms u_{i-1}-u_{i-2}, v_j-u_{k+1}, and u_{i+1}. Since Lemma 5.1 is used directly in the proof of Theorem 1.5, this needs to be corrected.","section":"Section 5, Lemma 5.1"}],"minor_comments":[{"comment":"In the first paragraph, 'compliment' should be 'complement'.","section":"Introduction"},{"comment":"The relabelling of cops in Step 2 is confusing: after defining C0 = C, the text says 'Let C↑ = C↑ and C↓ = C↓', which appears to be a typo or at least needs clearer notation for the two cops that remain at the ends of the old path.","section":"Section 3, proof of Theorem 1.2, Step 2"},{"comment":"In the last sentence of the C4 part, 'It follows that G is C4-free' should read 'It follows that H is C4-free'.","section":"Section 4, Lemma 4.2"},{"comment":"The claim that the cop-placement scheme guarantees a cop on every vertex of {u_1,u_2} ∪ {u_{i-2j} : j ≥ 0} ∪ {u_{i-1}} is asserted as 'trivial to verify' but is not proved by induction; given that the arrival schedule of cops at u_1 is described only qualitatively, a short induction or explicit schedule would improve verifiability.","section":"Section 5, proof of Theorem 1.5, Step 2"},{"comment":"The proof relies on Lemma 4.4 from [9] without reproving it; this is acceptable since it is an existing result, but the dependence should be stated more prominently because Theorem 1.4 is an immediate consequence of that lemma together with Theorem 1.2.","section":"Section 4, Theorem 1.3"}],"recommendation":"major_revision","confidential_remarks":"My independent reading agrees with the reader's positive assessment of the overall approach and of Theorems 1.2--1.4, but I am less optimistic about the current state of Theorem 1.5. The 'easy corollary' asserted at the Step 1/Step 2 boundary is not proved, and the proof of Lemma 5.1 contains a genuine vertex-count error. Both are fixable, but they should be addressed before publication. The manuscript is within the scope of the journal and the main ideas are sound enough to merit a major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about arXiv:2509.10941. First, it's a real contribution: Theorem 1.4 improves the Joret–Kamiński–Theis longest-path bound from p/2 to ceil(2p/3)+3 via a neat clique-substitution argument, and Theorem 1.5 extends Liu's (P_k,claw)-free bound to (P_k,E)-free graphs with a better constant, about k/2 instead of k. The flail lemmas are a sensible toolkit and the paper is honestly written.\n\nSecond, the main theorem has a gap. In the proof of Theorem 1.5, Step 1 ends by asserting that when the cops first get within distance 2, the robber is adjacent to the path w_0...w_t, called an 'easy corollary'. That's not proven and doesn't follow from the invariant. The invariant only guarantees some cop is at distance ≤2; the common neighbor could be outside the path. The deletion argument that keeps the robber inside the G_i graphs only works while distance ≥3, so at the first failure the robber can be in a deleted region, which could mean adjacent to a neighbor of a path vertex rather than to the path itself. The Step 2 pincer uses exactly the adjacency to w_q to place cops on w_{q-1} and w_{q+1} and start the chase. Without the adjacency, that setup doesn't get off the ground. So the paper needs a real argument here, not a handwave. It might be fixable, but as written it's a load-bearing gap.\n\nThere's also a small typo in Lemma 5.1: the listed vertex set has seven vertices but E has six; the intended set is clear and the lemma's proof works, so this is minor.\n\nThe rest of the paper holds up well on my read. The proof of Theorem 1.2 is long but the deductions are clear, aside from a terse 'without loss of generality' in Claim 4 that a referee should ask to be expanded. Theorem 1.3's clique substitution reduction is clean and the imported Lemma 4.4 is from earlier independent work, so no circularity.\n\nWho should read this: anyone working on cop number of graph classes defined by forbidden induced paths. It doesn't settle Sivaraman's conjecture, but it gives the best known bound for a significantly larger class than claw-free. I'd send it to a serious referee; the results are worth the referee time. My own recommendation would be a revision: close the Step 2 gap and expand Claim 4.","headline":"New bounds for (P_k,E)-free and longest-path graphs, but Theorem 1.5 has a gap at the Step 1-to-Step 2 transition that needs closing.","tokens_in":16590,"tokens_out":12870,"would_cite":false,"duration_ms":93146,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05C57","05C75"],"pacs":[],"model":"deepseek-v4-flash","headline":"Every graph avoiding an induced path on $k$ vertices and an induced claw with two subdivided edges is won by at most $\\lceil (k-1)/2\\rceil+3$ cops.","keywords":["cop number","Cops and Robbers","P_k-free graphs","E-free graphs","clique substitution","Gyárfás path argument","longest path","Sivaraman's conjecture"],"falsifier":"Construct a $(P_k,E)$-free graph with cop number greater than $\\lceil (k-1)/2\\rceil+3$, or a graph whose longest path has $p$ vertices and cop number greater than $\\lceil 2p/3\\rceil+3$; for the second, its clique substitution would then be a $(P_{2p+1},\\text{claw},\\text{butterfly},C_4,C_5)$-free graph with the same large cop number, directly contradicting Theorem 1.2. A smaller independent check is to compute the cop number of any graph and of its clique substitution: finding one with $c(G)>c(H)$ would break Lemma 4.4 and invalidate the reduction.","tokens_in":15389,"feed_emoji":"🚔","tokens_out":8314,"duration_ms":73564,"temperature":0.7,"pith_summary":"The paper establishes two concrete upper bounds on cop number, the minimum number of cops needed to guarantee capture of a robber. The main theorem says that if a graph contains no induced path on $k$ vertices and no induced copy of the graph $E$ (the claw with two subdivided edges), then its cop number is at most $\\lceil (k-1)/2\\rceil+3$, roughly $k/2$. For large $k$, this improves Liu's bound $k-3$ for the smaller class of $(P_k,\\text{claw})$-free graphs. A second theorem says that any graph whose longest path has $p$ vertices has cop number at most $\\lceil 2p/3\\rceil+3$, improving a bound of Joret, Kamiński, and Theis. Both results are steps toward Sivaraman's conjecture that every $P_k$-free graph has cop number at most $k-3$.","feed_headline":"Path-avoiding graphs need at most k/2 cops plus 3","feed_subtitle":"New bounds improve Liu's k−3 for claw-free graphs and also cover longest-path graphs.","key_machinery":"Two mechanisms carry the proof. First, the Gyárfás path argument: a lead cop walks along a path traced by the robber's previously occupied vertices while the other cops occupy every second or every third vertex of that path, with two extra cops guarding the start; the spacing turns the robber's safe play into an induced path, and the forbidden induced subgraphs are exactly the adjacencies that would otherwise let the robber keep one step ahead. Second, clique substitution: replace each vertex $v$ by a clique $K_v$ of size $\\deg(v)$, connecting cliques by one edge for each original edge; the resulting graph $H$ is $(C_4,C_5)$-free and, by the imported Lemma 4.4, satisfies $c(G)\\leq c(H)$. This operation translates a longest-path obstruction into a $(P_{2p+1},\\text{claw},\\text{butterfly},C_4,C_5)$-free graph, linking Theorem 1.2 to Theorem 1.4.","core_discovery":"The central assertion is Theorem 1.5: if $G$ is a $(P_k,E)$-free graph, where $E$ is the claw with two subdivided edges, then $c(G)\\leq \\lceil (k-1)/2\\rceil+3$. Since every claw-free graph is $E$-free, this recovers and, for large $k$, improves Liu's $k-3$ bound for $(P_k,\\text{claw})$-free graphs. The proof rests on a stronger intermediate statement, Theorem 1.2: every $(P_k,\\text{claw},\\text{butterfly},C_4,C_5)$-free graph has cop number at most $\\lceil (k-1)/3\\rceil+3$. A clique-substitution reduction then converts a graph with longest path of length $p$ and large cop number into such a forbidden-subgraph graph with parameter $2p+1$, yielding the longest-path bound $c(G)\\leq \\lceil 2p/3\\rceil+3$.","pith_inferences":["Beyond the paper: if Sivaraman's conjecture is true, extremal $P_k$-free graphs must contain an induced copy of $E$, because otherwise the main theorem would already give a bound stronger than $k-3$.","Beyond the paper: the additive constant $3$ appears to come from the three dedicated cops guarding the start and the distance-two capture step; a strategy that recycles those guards might lower the constant.","Beyond the paper: a denominator-$2$ version of the intermediate theorem would imply a longest-path bound of $p+O(1)$, matching the linear coefficient of the best known lower-bound construction.","Beyond the paper: since the whole longest-path theorem rests on the unproven Lemma 4.4, an elementary proof or a counterexample to that lemma would directly settle how much of Theorem 1.4 survives."],"forward_implications":["Every $(P_k,\\text{claw})$-free graph has cop number at most $\\lceil (k-1)/2\\rceil+3$, which for large $k$ is stronger than Liu's $k-3$.","Every graph whose longest path has $p$ vertices is $(\\lceil 2p/3\\rceil+3)$-cop-win, so any family of hard instances for the weak Meyniel conjecture would need cop number growing faster than linear in $p$ by only a small margin.","A counterexample to the main theorem would have to be a $(P_k,E)$-free graph with cop number exceeding about $k/2$, so it would have to avoid all the flail adjacencies the proof exploits.","The clique-substitution reduction in Theorem 1.3 means the longest-path theorem follows from the much more structured bound for $(P_k,\\text{claw},\\text{butterfly},C_4,C_5)$-free graphs.","The known examples of $P_k$-free graphs with cop number at least $\\lfloor (k-1)/2\\rfloor$ show that the linear coefficient in the new bounds cannot be pushed far below $1/2$ without additional assumptions."],"supporting_citations":[{"why":"Supplies the clique substitution operation and Lemma 4.4, whose preservation of cop number is the bridge in Theorem 1.3.","marker":"[9]"},{"why":"States Sivaraman's conjecture and the Gyárfás path argument that the capture strategies adapt.","marker":"[17]"},{"why":"Proved the $(P_k,\\text{claw})$-free bound $k-3$ that Theorem 1.5 generalizes and improves for large $k$.","marker":"[11]"},{"why":"Proved Sivaraman's conjecture for $P_5$-free graphs, providing the context and motivation for the new $P_k$-free classes.","marker":"[6]"},{"why":"Constructs $P_k$-free graphs with cop number at least $\\lfloor (k-1)/2\\rfloor$, the lower bound that indicates the order of the new upper bound.","marker":"[7]"},{"why":"Characterizes which finite sets of forbidden induced subgraphs force bounded cop number, placing the results in context.","marker":"[13]"},{"why":"Identifies the smallest graphs with cop numbers 2 and 3, used as tightness examples for the older bounds.","marker":"[3]"}],"fun_headline_variants":["Cops need only half the officers on path-free graphs","Improved cop bound for P_k,E-free graphs","Longest-path graphs get a better cop limit","Path-avoiding graphs need at most k/2+3 cops"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is the imported Lemma 4.4 that replacing every vertex by a clique does not decrease the cop number; the longest-path theorem follows from the forbidden-subgraph theorem only through that preservation step, and the paper does not reprove it.","fun_headline_variants_meta":{"raw":{"variants":["Cops need only half the officers on path-free graphs","Improved cop bound for P_k,E-free graphs","Longest-path graphs get a better cop limit","Path-avoiding graphs need at most k/2+3 cops"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.001166,"raw_usage":{"total_tokens":4856,"prompt_tokens":1008,"completion_tokens":3848,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":624,"completion_tokens_details":{"reasoning_tokens":3782}},"tokens_in":624,"tokens_out":3848,"duration_ms":25631,"temperature":1.0,"reasoning_tokens":3782,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T15:53:21.555103+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a $(P_k,E)$-free graph with cop number greater than $\\lceil (k-1)/2\\rceil+3$, or a graph whose longest path has $p$ vertices and cop number greater than $\\lceil 2p/3\\rceil+3$; for the second, its clique substitution would then be a $(P_{2p+1},\\text{claw},\\text{butterfly},C_4,C_5)$-free graph with the same large cop number, directly contradicting Theorem 1.2. A smaller independent check is to compute the cop number of any graph and of its clique substitution: finding one with $c(G)>c(H)$ would break Lemma 4.4 and invalidate the reduction.","supporting_citations":[{"cited_title":"Joret, M","cited_arxiv_id":null,"evidence_quote":"Supplies the clique substitution operation and Lemma 4.4, whose preservation of cop number is the bridge in Theorem 1.3."},{"cited_title":"Chudnovsky, S","cited_arxiv_id":null,"evidence_quote":"Proved Sivaraman's conjecture for $P_5$-free graphs, providing the context and motivation for the new $P_k$-free classes."},{"cited_title":"Cops and Robbers, Clique Covers, and Induced Cycles","cited_arxiv_id":"2507.14321","evidence_quote":"Constructs $P_k$-free graphs with cop number at least $\\lfloor (k-1)/2\\rfloor$, the lower bound that indicates the order of the new upper bound."},{"cited_title":"Masjoody and L","cited_arxiv_id":null,"evidence_quote":"Characterizes which finite sets of forbidden induced subgraphs force bounded cop number, placing the results in context."},{"cited_title":"Baird, A","cited_arxiv_id":null,"evidence_quote":"Identifies the smallest graphs with cop numbers 2 and 3, used as tightness examples for the older bounds."}],"review_version":2}