Knocking out Pk-free graphs

A parallel knock-out scheme for a graph proceeds in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is KO-reducible if there exists such a scheme that eliminates every vertex in the graph. The Parallel Knock-Out problem is to decide whether a graph G is KO-reducible. This problem is known to be NP-complete and has been studied for several graph classes. We show that the problem is NP-complete even for split graphs, a subclass of P5-free graphs. In contrast, our main result is that it is linear-time solvable for P4-free graphs (cographs).