We use cookies to ensure that we give you the best experience on our website. You can change your cookie settings at any time. Otherwise, we'll assume you're OK to continue.

Durham Research Online
You are in:

Computing sharp 2-factors in claw-free graphs.

Broersma, H.J. and Paulusma, Daniel (2008) 'Computing sharp 2-factors in claw-free graphs.', in Mathematical foundations of computer science 2008, 33rd International Symposium, MFCS 2008, 25-29 August 2008, Toru´n, Poland ; proceedings. Berlin ; Heidelberg: Springer, pp. 193-204. Lecture notes in computer science. (5162).


In a recently submitted 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 & Schelp.

Item Type:Book chapter
Full text:Full text not available from this repository.
Publisher Web site:
Record Created:07 Oct 2010 12:35
Last Modified:03 Apr 2013 13:22

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