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ácek, Saito and Schelp.
Original language | English |
---|---|
Article number | 10.1016/j.jda.2009.07.001 |
Pages (from-to) | 321-329 |
Number of pages | 9 |
Journal | Journal of discrete algorithms |
Volume | 8 |
Issue number | 3 |
DOIs | |
Publication status | Published - Sep 2010 |
Event | 33rd International Symposium on Mathematical Foundations of Computer Science, MFCS 2008: Mathematical Foundations of Computer Science - Torun, Poland, Torun, Poland Duration: 25 Aug 2008 → 29 Aug 2008 Conference number: 33 |