We use cookies to ensure that we give you the best experience on our website. By continuing to browse this repository, you give consent for essential cookies to be used. You can read more about our Privacy and Cookie Policy.

Durham Research Online
You are in:

Knocking out Pk-free graphs.

Johnson, Matthew and Paulusma, Daniël and Stewart, Anthony (2015) 'Knocking out Pk-free graphs.', Discrete applied mathematics., 190-191 . pp. 100-108.


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

Item Type:Article
Keywords:Parallel knock-out schemes, Hamilton cycle, Cographs, Split graphs, Computational complexity.
Full text:(AM) Accepted Manuscript
Download PDF
Publisher Web site:
Publisher 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.
Date accepted:17 April 2015
Date deposited:19 May 2015
Date of first online publication:August 2015
Date first made open access:08 May 2016

Save or Share this output

Look up in GoogleScholar