← All problems

Liu’s cop-number conjecture for P_k-free graphs

For every integer k≥4k\ge 4 and every finite connected graph GG with no induced subgraph isomorphic to the path PkP_k, the cop number satisfies c(G)≤k−3c(G)\le k-3.

References

Source: arXiv

Progress summary

Refreshed
Open · progress reported

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 PkP_k-free graph has cop number at most k−3k-3. Liu established important restricted cases, but the unrestricted conjecture remains open for k≥6k \ge 6.

Known results

  • Liu, 2019: the conjecture holds for connected (Pk,H)(P_k,H)-free graphs when HH is a claw or a cycle of length at most kk.
  • Chudnovsky, Norin, Seymour, and Turcotte: the P5P_5-free case is proved.
  • Earlier work established further restricted subclasses, including bounds for graphs excluding a claw, butterfly, C4C_4, and C5C_5.

October 14, 2026 restricted-class bounds

Gupta, Pradhan, and Swain report that (Pk,claw)(P_k,\text{claw})-free graphs have cop number at most ⌈(k−1)/2⌉\lceil (k-1)/2\rceil, with ⌈k/3⌉\lceil k/3\rceil under an additional hole condition; (Pk,fork)(P_k,\text{fork})-free graphs have bound ⌈2(k−1)/3⌉\lceil 2(k-1)/3\rceil, and the (P7,fork)(P_7,\text{fork})-free bound 33 is tight. These are claimed advances, not a proof of the general conjecture.

Current status (as of October 2026): The P5P_5 case and several restricted classes are settled, but the conjectured bound c(G)≤k−3c(G)\le k-3 for general PkP_k-free graphs with k≥6k\ge 6 remains open.

Sources

Solutions 0

No solutions have been posted yet.