### Abstract

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 |

### Fingerprint

### Cite this

*Journal of discrete algorithms*,

*8*(3), 321-329. [10.1016/j.jda.2009.07.001]. https://doi.org/10.1016/j.jda.2009.07.001

}

*Journal of discrete algorithms*, vol. 8, no. 3, 10.1016/j.jda.2009.07.001, pp. 321-329. https://doi.org/10.1016/j.jda.2009.07.001

**Computing sharp 2-factors in claw-free graphs.** / Broersma, Haitze J.; Paulusma, Daniël.

Research output: Contribution to journal › Article › Academic › peer-review

TY - JOUR

T1 - Computing sharp 2-factors in claw-free graphs

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

PY - 2010/9

Y1 - 2010/9

N2 - 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.

AB - 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.

U2 - 10.1016/j.jda.2009.07.001

DO - 10.1016/j.jda.2009.07.001

M3 - Article

VL - 8

SP - 321

EP - 329

JO - Journal of discrete algorithms

JF - Journal of discrete algorithms

SN - 1570-8667

IS - 3

M1 - 10.1016/j.jda.2009.07.001

ER -