# Computing sharp 2-factors in claw-free graphs

Broersma, H.J.
and
Paulusma, D.
(2008)
*Computing sharp 2-factors in claw-free graphs.*
In: 33rd International Symposium on Mathematical Foundations of Computer Science, August 27-31, 2008, Torun, Poland (pp. pp. 193-204).

PDF
Restricted to UT campus only : Request a copy 460kB |

Abstract: | 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: | Conference or Workshop Item |

Faculty: | Electrical Engineering, Mathematics and Computer Science (EEMCS) |

Research Group: | |

Link to this item: | http://purl.utwente.nl/publications/62551 |

Official URL: | http://dx.doi.org/10.1007/978-3-540-85238-4_15 |

Export this item as: | BibTeX EndNote HTML Citation Reference Manager |

Repository Staff Only: item control page

Metis ID: 254914