Cops and robbers on P_5-free graphs

01/30/2023
by   Maria Chudnovsky, et al.
0

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

Please sign up or login with your details

Forgot password? Click here to reset