Liu’s cop-number conjecture for P_k-free graphs
For every integer and every finite connected graph with no induced subgraph isomorphic to the path , the cop number satisfies .
References
- Cop number of P_k-free graphs without a claw or a fork — arXiv — Uttam K. Gupta, Dinabandhu Pradhan, Rashmi Rekha Swain
Source: arXiv
Progress summary
The general bound remains open, while a new paper improves it for graphs avoiding extra small patterns.
Sivaraman’s 2019 conjecture asks whether every connected -free graph has cop number at most . Liu established important restricted cases, but the unrestricted conjecture remains open for .
Known results
- Liu, 2019: the conjecture holds for connected -free graphs when is a claw or a cycle of length at most .
- Chudnovsky, Norin, Seymour, and Turcotte: the -free case is proved.
- Earlier work established further restricted subclasses, including bounds for graphs excluding a claw, butterfly, , and .
October 14, 2026 restricted-class bounds
Gupta, Pradhan, and Swain report that -free graphs have cop number at most , with under an additional hole condition; -free graphs have bound , and the -free bound is tight. These are claimed advances, not a proof of the general conjecture.
Current status (as of October 2026): The case and several restricted classes are settled, but the conjectured bound for general -free graphs with remains open.
Solutions 0
No solutions have been posted yet.