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).
|Keywords:||Parallel knock-out schemes, Hamilton cycle, Cographs, Split graphs, Computational complexity.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (351Kb)
|Publisher Web site:||http://dx.doi.org/10.1016/j.dam.2015.04.010|
|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|