Sivaraman–Testa conjecture on the cop number of induced-path-free graphs

Let GG be a connected graph, and let PtP_t denote the path on tt vertices. A graph is PtP_t-free if it has no induced subgraph isomorphic to PtP_t, and c(G)c(G) denotes its cop number. Sivaraman–Testa conjecture. For t5t\geq 5, if GG is PtP_t-free, then

c(G)t3.c(G)\leq t-3.

This improves by one the previously known bound c(G)t2c(G)\leq t-2 for connected PtP_t-free graphs. The conjecture is presented as an improvement of that bound; its resolution is not specified in the supplied text.

Sources & referencesView supporting material

Primary source

Jérémie Turcotte, “Cops and robbers on 2K_2-free graphs”, arXiv:2001.03124 (2021).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.