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

Broersma, H.J.; Paulusma, D.; Yoshimoto, K.

doi:10.1007/s00373-009-0855-7

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

Broersma, H.J.; Paulusma, D.; Yoshimoto, K.

Authors

H.J. Broersma

Professor Daniel Paulusma daniel.paulusma@durham.ac.uk
Professor

K. Yoshimoto

Abstract

Let G be a claw-free graph with order n and minimum degree δ. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. If δ = 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 δ ≥ 5, then G has a 2-factor with at most (n − 3)/(δ − 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 δ − 1 by δ, respectively.

Citation

Broersma, H., Paulusma, D., & Yoshimoto, K. (2009). Sharp upper bounds for the minimum number of components of 2-factors in claw-free graphs. Graphs and Combinatorics, 25(4), 427-460. https://doi.org/10.1007/s00373-009-0855-7

Journal Article Type	Article
Publication Date	Nov 1, 2009
Deposit Date	Dec 15, 2009
Publicly Available Date	Jan 22, 2015
Journal	Graphs and Combinatorics
Print ISSN	0911-0119
Electronic ISSN	1435-5914
Publisher	Springer
Peer Reviewed	Peer Reviewed
Volume	25
Issue	4
Pages	427-460
DOI	https://doi.org/10.1007/s00373-009-0855-7
Keywords	Claw-free graph, 2-factor, Minimum degree, Edge-degree.
Public URL	https://durham-repository.worktribe.com/output/1554922
Publisher URL	http://www.springerlink.com/content/1wl54587m80j5511/