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

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

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/