On components of 2-factors in claw-free graphs

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

Abstract

For a non-hamiltonian claw-free graph G with order n and minimum degree δ we show the following. 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. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor δ−1 by δ.

Citation

Broersma, H., Paulusma, D., & Yoshimoto, K. On components of 2-factors in claw-free graphs. Presented at European Conference on Combinatorics, Graph Theory and Applications

• Presentation Conference Type: Conference Paper (published)
• Conference Name: European Conference on Combinatorics, Graph Theory and Applications
• Publication Date: Aug 1, 2007
• Deposit Date: Dec 21, 2014
• Journal: Electronic Notes in Discrete Mathematics
• Print ISSN: 1571-0653
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 29
• Pages: 289-293
• DOI: https://doi.org/10.1016/j.endm.2007.07.050
• Keywords: Claw-free graph, 2-factor, Minimum degree, Edge degree
• Public URL: https://durham-repository.worktribe.com/output/1153840