Skip to main content

Research Repository

Advanced Search

Knocking out P_k-free graphs

Johnson, M.; Paulusma, D.; Stewart, A.

Knocking out P_k-free graphs Thumbnail


A. Stewart


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).


Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108.

Journal Article Type Article
Acceptance Date Apr 17, 2015
Publication Date Aug 20, 2015
Deposit Date May 12, 2015
Publicly Available Date May 8, 2016
Journal Discrete Applied Mathematics
Print ISSN 0166-218X
Publisher Elsevier
Peer Reviewed Peer Reviewed
Volume 190-191
Pages 100-108
Keywords Parallel knock-out schemes, Hamilton cycle, Cographs, Split graphs, Computational complexity.


Accepted Journal Article (359 Kb)

Copyright Statement
NOTICE: this is the author’s version of a work that was accepted for publication in Discrete Applied Mathematics. Changes resulting from the publishing process, such as peer review, editing, corrections, structural formatting, and other quality control mechanisms may not be reflected in this document. Changes may have been made to this work since it was submitted for publication. A definitive version was subsequently published in Discrete Applied Mathematics, 190-191, 20 August 2015, 10.1016/j.dam.2015.04.010.

You might also like

Downloadable Citations