Skip to main content

Research Repository

Advanced Search

On components of 2-factors in claw-free graphs

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

Authors

H.J. Broersma

K. Yoshimoto



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. (2007). On components of 2-factors in claw-free graphs. Electronic Notes in Discrete Mathematics, 29, 289-293. https://doi.org/10.1016/j.endm.2007.07.050

Journal Article Type Conference Paper
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


You might also like



Downloadable Citations