Knocking out P_k-free graphs

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

doi:10.1016/j.dam.2015.04.010

Knocking out P_k-free graphs

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

Authors

Professor Matthew Johnson matthew.johnson2@durham.ac.uk
Head Of Department

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

A. Stewart

Abstract

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

Citation

Johnson, M., Paulusma, D., & Stewart, A. (2015). Knocking out P_k-free graphs. Discrete Applied Mathematics, 190-191, 100-108. https://doi.org/10.1016/j.dam.2015.04.010

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
DOI	https://doi.org/10.1016/j.dam.2015.04.010
Keywords	Parallel knock-out schemes, Hamilton cycle, Cographs, Split graphs, Computational complexity.

Files

Accepted Journal Article (359 Kb)
PDF

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.