Cops and Robbers on Graphs with Path Constraints

Alexander Clow; Erin Meger

REVIEW 2 major objections 5 minor 22 references

Cops and Robbers on Graphs with Path Constraints

T0 review · 2 major / 5 minor · reviewed 2026-08-15 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict 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. read the letter →

arxiv 2509.10941 v1 pith:ZBWXJD3E submitted 2025-09-13 math.CO

Alexander Clow , Erin Meger This is my paper · ORCID

classification math.CO MSC 05C5705C75

keywords copnumberCopsandRobbersP_k-freegraphsE-freecliquesubstitutionGyárfáspathargumentlongestSivaraman'sconjecture

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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$.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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$.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the 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.

Second, 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.

There'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.

The 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.

Who 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.

Referee Report

2 major / 5 minor

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.

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 (2)

[Section 5, proof of Theorem 1.5, Step 1 to Step 2] 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 5, Lemma 5.1] 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.

minor comments (5)

[Introduction] In the first paragraph, 'compliment' should be 'complement'.
[Section 3, proof of Theorem 1.2, Step 2] 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 4, Lemma 4.2] 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 5, proof of Theorem 1.5, Step 2] 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 4, Theorem 1.3] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circular derivation: the paper proves its upper bounds by explicit cop strategies, relies on an independent external lemma for clique substitution, and uses self-citation only for context.

full rationale

Score 0. The central bounds (Theorems 1.2, 1.4, and 1.5) are derived by explicit cop-movement strategies rather than by fitting parameters or assuming the conclusion. In Theorem 1.2, the cops' Gyárfás walk is generated from the graph, the bound ceil((k-1)/3)+3 is exactly the number of labelled cops used, and the proof shows that failure to capture produces an induced P_k, contradicting P_k-freeness. Theorem 1.3's reduction uses the clique substitution operation and cites Lemma 4.4 (c(G) <= c(H)) from Joret, Kamiński, and Theis [9]; that lemma is independent prior work, is not a self-citation, and is not redefined in terms of the paper's results. Theorem 1.4 then combines these independent ingredients; it does not presuppose its own bound. Theorem 1.5 similarly constructs a strategy with ceil((k-1)/2)+3 cops and proves that if the robber avoids capture long enough, an induced P_k or an induced E appears. The only self-citation, [7], is used in the introduction for lower-bound context and again in the future-work discussion; it is never load-bearing for the upper bounds. The paper's Step 2 assertion in Theorem 1.5 that adjacency of the robber to the cops' path is 'an easy corollary of the argument' is an unproved proof gap, not a circular reduction, and the seven-vertex display in Lemma 5.1 is a possible correctness/typo issue; neither makes the claimed derivation equivalent to its inputs. No equation is defined in terms of the result it predicts, and no fitted value is relabelled as a prediction.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No free parameters are fitted to data; this is a pure combinatorial proof. The only external black box is the clique-substitution lemma from [9]. The new term 'flail' is a definitional device, not an invented physical or mathematical entity requiring independent evidence.

assumptions (2)

standard math Clique substitution preserves cop number in the lower-bound direction: c(G) ≤ c(H) for H the clique substitution of G.
Imported as Lemma 4.4 from [9]; used in Theorem 1.3 to transfer c(G) ≥ t to c(H) ≥ t.
domain assumption All graphs are finite and connected unless stated otherwise; cops and robber may pass on a turn.
Standard Cops and Robbers convention used throughout; finiteness is needed for the termination arguments in the proofs.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Cops and Robbers on Graphs with Path Constraints." pith.science (2026). https://pith.science/paper/ZBWXJD3E

@misc{pith2026250910941,
  author       = {Pith},
  title        = {Pith review of: Cops and Robbers on Graphs with Path Constraints},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ZBWXJD3E}},
  note         = {Machine review of arXiv:2509.10941}
}

abstract

In 2019, Sivaraman conjectured that every $P_k$-free graph has cop number at most $k-3$. In the same year, Liu proved this conjecture for $(P_k,\text{claw})$-free graphs. Recently Chudnovsky, Norin, Seymour, and Turcotte proved this conjecture for $P_5$-free graphs. For $k\geq 6$ the conjecture remains widely opened. Let the $E$ graph be the $\text{claw}$ with two subdivided edges. We show that all $(P_k,E)$-free graphs have cop number at most $\lceil \frac{k-1}{2} \rceil +3$, which improves and generalizes Liu's result for $(P_k,\text{claw})$-free graphs. We also prove that if $G$ is a graph whose longest path is length $p$, then $G$ has cop number at most $\lceil \frac{2p}{3} \rceil+3$. This improves a bound of Joret, Kami\'nski, and Theis. Our proof relies on demonstrating that all $(P_k,\text{claw},\text{butterfly},C_4,C_5)$-free graphs have cop number at most $\lceil\frac{k-1}{3}\rceil +3$.

Figures

Figures reproduced from arXiv: 2509.10941 by the authors.

**Figure 1.** From left to right the claw, E, and butterfly graphs are shown. It is standard to consider classes of graphs defined by forbidden substructures such as minors or induced subgraphs. A graph G is H-free or H-minor free if G does not contain, respectively, any induced subgraph or minor which is isomorphic to H. Of particular importance for this paper will be the class of Pk-free graphs. Also of note are graph with ind… view at source ↗

**Figure 2.** An example of a (3, 4, S)-flail where S = {(1, 1),(2, 3),(3, 2),(3, 3),(3, 4)}. Let P : u1 . . . uk be a path and X be a subset of the vertices {u1, . . . , uk}. We say that X 1 3 -saturates P if for all i, X ∩ {ui , ui+1} ̸= ∅ or ui−1, ui+2 ∈ X. Notice the second clause cannot be fulfilled if i = 1, so X being 1 3 -saturating implies u1 or u2 is in X. Intuitively, every consecutive set of three vertices has at leas… view at source ↗

**Figure 3.** The 4-wheel is drawn on the left and the clique substitution of the 4-wheel is [PITH_FULL_IMAGE:figures/full_fig_p005_3.png] view at source ↗

Figures from the paper (3 more)

**Figure 4.** Figure 4: The left figure depicts the flail discussed in Lemma 3.1, while the right figure [PITH_FULL_IMAGE:figures/full_fig_p006_4.png]

**Figure 5.** Figure 5: An image of how cops other than C 0 move on turn i = 3a < M. Here the walk u0 . . . ui need not be internally vertex disjoint from the path w0 . . . wt . Claim 1: For all i ≥ 3 before the cops move on turn i + 1, there is a cop C occupying u0 which remains on u0 in tur…

**Figure 6.** Figure 6: The figure depicts the flail discussed in Lemma 5.1. The lemmas claim at least [PITH_FULL_IMAGE:figures/full_fig_p014_6.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

22 extracted references · 18 canonical work pages

[9]

Joret, M

G. Joret, M. Kami´ nski, and D. O. Theis. The Cops and Robber game on graphs with forbidden (induced) subgraphs.Contributions to Discrete Mathematics, 5(2), 2010

work page 2010
[1]

Aigner and M

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]

Baird, A

W. Baird, A. Beveridge, A. Bonato, P. Codenotti, A. Maurer, J. Mccauley, and S. Val- eva. On the minimum order ofk-cop-win graphs.Contributions to Discrete Mathematics, 9(1):70–84, 2014

work page 2014
[4]

Bonato and R

A. Bonato and R. Nowakowski.The game of Cops and Robbers on graphs. American Mathematical Soc., 2011

work page 2011
[5]

A. Char, P. V. Maniya, and D. Pradhan. 4K 1-free graph with the cop number 3.arXiv preprint arXiv:2505.15416, 2025

arXiv 2025
[6]

Chudnovsky, S

M. Chudnovsky, S. Norin, P. D. Seymour, and J. Turcotte. Cops and Robbers onP 5-free graphs.SIAM Journal on Discrete Mathematics, 38(1):845–856, 2024

work page 2024
[7]

Cops and Robbers, Clique Covers, and Induced Cycles

A. Clow and I. Zaguia. Cops and robbers, clique covers, and induced cycles.arXiv preprint arXiv:2507.14321, 2025

work page Pith review arXiv 2025

Show all 22 references

[8]

U. K. Gupta, S. Mishra, and D. Pradhan. Cops and robber on subclasses of p5-free graphs.Discrete Mathematics, 346(6):113353, 2023. 17

2023
[10]

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
[11]

M. Liu. The cop number of graphs with forbidden induced subgraphs.arXiv preprint arXiv:1908.11478, 2019

1908 arXiv
[12]

Lu and X

L. Lu and X. Peng. On meyniel’s conjecture of the cop number.Journal of Graph Theory, 71(2):192–205, 2012

2012
[13]

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
[14]

Nowakowski and P

R. Nowakowski and P. Winkler. Vertex-to-vertex pursuit in a graph.Discrete Mathe- matics, 43(2-3):235–239, 1983

1983
[15]

J. Petr, J. Portier, and L. Versteegen. A note on cops and robbers, independence number, domination number and diameter.Discrete Mathematics, 346(1):113175, 2023

2023
[16]

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
[17]

Sivaraman

V. Sivaraman. An application of the Gy´ arf´ as path argument.Discrete Mathematics, 342(8):2306–2307, 2019

2019
[18]

Sivaraman and S

V. Sivaraman and S. Testa. Cop number of 2K 2-free graphs.arXiv preprint arXiv:1903.11484, 2019

1903 arXiv
[19]

Turcotte

J. Turcotte. Cops and Robbers on 2K 2-free graphs.Discrete Mathematics, 345(1):112660, 2022

2022
[20]

Turcotte and S

J. Turcotte and S. Yvon. 4-cop-win graphs have at least 19 vertices.Discrete Applied Mathematics, 301:74–98, 2021

2021
[21]

Z. A. Wagner. Cops and robbers on diameter two graphs.Discrete Mathematics, 338(3):107–109, 2015

2015
[22]

D. B. West.Introduction to Graph Theory, volume 2. Prentice hall Upper Saddle River, 2001. 18

2001

Pith tools

Reviewed August 15, 2026 · model on record in the stance chip above.

[1] [9]

Joret, M

G. Joret, M. Kami´ nski, and D. O. Theis. The Cops and Robber game on graphs with forbidden (induced) subgraphs.Contributions to Discrete Mathematics, 5(2), 2010

work page 2010

[2] [1]

Aigner and M

M. Aigner and M. Fromme. A game of Cops and Robbers.Discrete Applied Mathematics, 8(1):1–12, 1984

work page 1984

[3] [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

[4] [3]

Baird, A

W. Baird, A. Beveridge, A. Bonato, P. Codenotti, A. Maurer, J. Mccauley, and S. Val- eva. On the minimum order ofk-cop-win graphs.Contributions to Discrete Mathematics, 9(1):70–84, 2014

work page 2014

[5] [4]

Bonato and R

A. Bonato and R. Nowakowski.The game of Cops and Robbers on graphs. American Mathematical Soc., 2011

work page 2011

[6] [5]

A. Char, P. V. Maniya, and D. Pradhan. 4K 1-free graph with the cop number 3.arXiv preprint arXiv:2505.15416, 2025

arXiv 2025

[7] [6]

Chudnovsky, S

M. Chudnovsky, S. Norin, P. D. Seymour, and J. Turcotte. Cops and Robbers onP 5-free graphs.SIAM Journal on Discrete Mathematics, 38(1):845–856, 2024

work page 2024

[8] [7]

Cops and Robbers, Clique Covers, and Induced Cycles

A. Clow and I. Zaguia. Cops and robbers, clique covers, and induced cycles.arXiv preprint arXiv:2507.14321, 2025

work page Pith review arXiv 2025