Cops and robbers on P_5-free graphs
We prove that every connected P_5-free graph has cop number at most two, solving a conjecture of Sivaraman. In order to do so, we first prove that every connected P_5-free graph G with independence number at least three contains a three-vertex induced path with vertices a - b - c in order, such that every neighbour of c is also adjacent to one of a,b.
READ FULL TEXT