Publication details for Professor Matthew JohnsonJohnson, M., Paulusma, D. & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics 190-191: 100-108.
- Publication type: Journal Article
- ISSN/ISBN: 0166-218X (print)
- DOI: 10.1016/j.dam.2015.04.010
- Keywords: Parallel knock-out schemes, Hamilton cycle, Cographs, Split graphs, Computational complexity.
- Further publication details on publisher web site
- Durham Research Online (DRO) - may include full text
Author(s) from Durham
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 GG 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 P5P5-free graphs. In contrast, our main result is that it is linear-time solvable for P4P4-free graphs (cographs).