Cops and Robbers on \(\boldsymbol{P_5}\)-Free Graphs
Maria Chudnovsky, Sergey Norin, Paul D. Seymour, Jérémie Turcotte · SIAM Journal on Discrete Mathematics · 2024
Abstract. We prove that every connected [Formula: see text]-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected [Formula: see text]-free graph [Formula: see text] with independence number at least three contains a three-vertex induced path with vertices [Formula: see text] in order, such that every neighbor of [Formula: see text] is also adjacent to one of [Formula: see text].