Path factors and parallel knock-out schemes of almost claw-free graphs

Johnson, M.; Paulusma, D.; Wood, C.

doi:10.1016/j.disc.2009.04.022

Path factors and parallel knock-out schemes of almost claw-free graphs

Johnson, M.; Paulusma, D.; Wood, C.

Authors

M. Johnson

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

C. Wood

Abstract

An H1,{H2}-factor of a graph G is a spanning subgraph of G with exactly one component isomorphic to the graph H1 and all other components (if there are any) isomorphic to the graph H2. We completely characterise the class of connected almost claw-free graphs that have a P7,{P2}-factor, where P7 and P2 denote the paths on seven and two vertices, respectively. We apply this result to parallel knock-out schemes for almost claw-free graphs. These schemes proceed in rounds in each of which each surviving vertex eliminates one of its surviving neighbours. A graph is reducible if such a scheme eliminates every vertex in the graph. Using our characterisation, we are able to classify all reducible almost claw-free graphs, and we can show that every reducible almost claw-free graph is reducible in at most two rounds. This leads to a quadratic time algorithm for determining if an almost claw-free graph is reducible (which is a generalisation and improvement upon the previous strongest result that showed that there was a O(n5.376) time algorithm for claw-free graphs on n vertices).

Citation

Johnson, M., Paulusma, D., & Wood, C. (2010). Path factors and parallel knock-out schemes of almost claw-free graphs. Discrete Mathematics, 310(9), 1413-1423. https://doi.org/10.1016/j.disc.2009.04.022

Journal Article Type	Article
Publication Date	May 6, 2010
Deposit Date	Oct 6, 2010
Publicly Available Date	Oct 29, 2010
Journal	Discrete mathematics.
Print ISSN	0012-365X
Publisher	Elsevier
Peer Reviewed	Peer Reviewed
Volume	310
Issue	9
Pages	1413-1423
DOI	https://doi.org/10.1016/j.disc.2009.04.022
Keywords	Parallel knock-out schemes, (almost) claw-free graphs, Perfect matching, Factor.
Public URL	https://durham-repository.worktribe.com/output/1538947

Files

Accepted Journal Article (343 Kb)
PDF

Copyright Statement
NOTICE: this is the author's version of a work that was accepted for publication in Discrete 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 Mathematics, 310, 9, 6 May 2010, 10.1016/j.disc.2009.04.022.