Computing sharp 2-factors in claw-free graphs

Broersma, Hajo and Paulusma, Daniël (2010) Computing sharp 2-factors in claw-free graphs. Journal of Discrete Algorithms, 8 (3). pp. 321-329. ISSN 1570-8667

PDF
Restricted to UT campus only: Request a copy
213Kb

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
Copyright:	© 2009 Elsevier B.V.
Faculty:	Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:	Discrete Mathematics and Mathematical Programming (DMMP)
Link to this item:	http://purl.utwente.nl/publications/72447
Official URL:	http://dx.doi.org/10.1016/j.jda.2009.07.001
Export this item as:	BibTeX EndNote HTML Citation Reference Manager

Show download statistics for this publication

Repository Staff Only: item control page