Cookies

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:

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

Johnson, M. and Paulusma, Daniel and Wood, C. (2010) 'Path factors and parallel knock-out schemes of almost claw-free graphs.', Discrete mathematics., 310 (9). pp. 1413-1423.

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

Item Type:Article
Full text:PDF - Accepted Version (335Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.disc.2009.04.022
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Discrete mathematics.
Record Created:06 Oct 2010 12:05
Last Modified:03 Apr 2013 13:15

Social bookmarking: del.icio.usConnoteaBibSonomyCiteULikeFacebookTwitterExport: EndNote, Zotero | BibTex
Usage statisticsLook up in GoogleScholar | Find in a UK Library