### Abstract

Original language | Undefined |
---|---|

Title of host publication | 33rd International Symposium on Mathematical Foundations of Computer Science |

Place of Publication | Berlin |

Publisher | Springer |

Pages | 193-204 |

Number of pages | 12 |

ISBN (Print) | 978-3-540-85237-7 |

DOIs | |

Publication status | Published - Aug 2008 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer Verlag |

Number | WoTUG-31 |

Volume | 5162 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Keywords

- EWI-14142
- IR-62551
- METIS-254914

### Cite this

*33rd International Symposium on Mathematical Foundations of Computer Science*(pp. 193-204). [10.1007/978-3-540-85238-4_15] (Lecture Notes in Computer Science; Vol. 5162, No. WoTUG-31). Berlin: Springer. https://doi.org/10.1007/978-3-540-85238-4_15

}

*33rd International Symposium on Mathematical Foundations of Computer Science.*, 10.1007/978-3-540-85238-4_15, Lecture Notes in Computer Science, no. WoTUG-31, vol. 5162, Springer, Berlin, pp. 193-204. https://doi.org/10.1007/978-3-540-85238-4_15

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

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

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

N1 - 10.1007/978-3-540-85238-4_15

PY - 2008/8

Y1 - 2008/8

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

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

KW - EWI-14142

KW - IR-62551

KW - METIS-254914

U2 - 10.1007/978-3-540-85238-4_15

DO - 10.1007/978-3-540-85238-4_15

M3 - Conference contribution

SN - 978-3-540-85237-7

T3 - Lecture Notes in Computer Science

SP - 193

EP - 204

BT - 33rd International Symposium on Mathematical Foundations of Computer Science

PB - Springer

CY - Berlin

ER -