Broersma, H.J. and Paulusma, Daniel (2010) 'Computing sharp 2-factors in claw-free graphs.', Journal of discrete algorithms., 8 (3). pp. 321-329.
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.
|Keywords:||Claw-free graph, 2-factor, Number of components, Polynomial algorithm.|
|Full text:||(AM) Accepted Manuscript|
Download PDF (183Kb)
|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:||Export: EndNote, Zotero | BibTex|
|Look up in GoogleScholar | Find in a UK Library|