### Abstract

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

Article number | 10.1007/s00373-009-0855-7 |

Pages (from-to) | 427-460 |

Number of pages | 34 |

Journal | Graphs and combinatorics |

Volume | 25 |

Issue number | 4 |

DOIs | |

Publication status | Published - 2009 |

### Keywords

- EWI-17516
- IR-70041
- METIS-265816

### Cite this

*Graphs and combinatorics*,

*25*(4), 427-460. [10.1007/s00373-009-0855-7]. https://doi.org/10.1007/s00373-009-0855-7

}

*Graphs and combinatorics*, vol. 25, no. 4, 10.1007/s00373-009-0855-7, pp. 427-460. https://doi.org/10.1007/s00373-009-0855-7

**Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs.** / Broersma, Haitze J.; Paulusma, Daniël; Yoshimoto, Kiyoshi.

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

TY - JOUR

T1 - Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs

AU - Broersma, Haitze J.

AU - Paulusma, Daniël

AU - Yoshimoto, Kiyoshi

N1 - 10.1007/s00373-009-0855-7

PY - 2009

Y1 - 2009

N2 - Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 4$, then $G$ has a 2-factor with at most $(5n - 14)/ 18$ components, unless $G$ belongs to a finite class of exceptional graphs. If $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 1)$ components, unless $G$ is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace $\delta - 1$ by $\delta$, respectively.

AB - Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If $\delta = 4$, then $G$ has a 2-factor with at most $(5n - 14)/ 18$ components, unless $G$ belongs to a finite class of exceptional graphs. If $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 1)$ components, unless $G$ is a complete graph. These bounds are best possible in the sense that we cannot replace 5/18 by a smaller quotient and we cannot replace $\delta - 1$ by $\delta$, respectively.

KW - EWI-17516

KW - IR-70041

KW - METIS-265816

U2 - 10.1007/s00373-009-0855-7

DO - 10.1007/s00373-009-0855-7

M3 - Article

VL - 25

SP - 427

EP - 460

JO - Graphs and combinatorics

JF - Graphs and combinatorics

SN - 0911-0119

IS - 4

M1 - 10.1007/s00373-009-0855-7

ER -