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:

Computing sharp 2-factors in claw-free graphs.

Broersma, H.J. and Paulusma, Daniel (2010) 'Computing sharp 2-factors in claw-free graphs.', Journal of discrete algorithms., 8 (3). pp. 321-329.

Abstract

In a previous paper we obtained an upper bound for the minimum number of components of a 2-factor in a claw-free graph. This bound is sharp in the sense that there exist infinitely many claw-free graphs for which the bound is tight. In this paper we extend these results by presenting a polynomial algorithm that constructs a 2-factor of a claw-free graph with minimum degree at least four whose number of components meets this bound. As a byproduct we show that the problem of obtaining a minimum 2-factor (if it exists) is polynomially solvable for a subclass of claw-free graphs. As another byproduct we give a short constructive proof for a result of Ryjáček, Saito and Schelp.

Item Type:Article
Keywords:Claw-free graph, 2-factor, Number of components, Polynomial algorithm.
Full text:PDF - Accepted Version (183Kb)
Status:Peer-reviewed
Publisher Web site:http://dx.doi.org/10.1016/j.jda.2009.07.001
Publisher statement:NOTICE: this is the author's version of a work that was accepted for publication in Journal of discrete algorithms.
Record Created:06 Oct 2010 12:35
Last Modified:03 Apr 2013 13:16

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