On components of 2-factors in claw-free graphs


Broersma, H.J. and Paulusma, D. and Yoshimoto, K. (2007) On components of 2-factors in claw-free graphs. In: EuroComb 2007: European Conference on Combinatorics, Graph Theory and Applications, 11-15 September 2007, Seville, Spain (pp. pp. 289-293).

[img] PDF
Restricted to UT campus only
: Request a copy
Abstract:For a non-hamiltonian claw-free graph $G$ with order $n$ and minimum degree $\delta$ we show the following. 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 $\delta \ge 5$, then $G$ has a 2-factor with at most $(n-3)/(\delta -1)$ components. These bounds are sharp in the sense that we can replace nor 5/18 by a smaller quotient nor $\delta -1$ by $\delta$.
Item Type:Conference or Workshop Item
Electrical Engineering, Mathematics and Computer Science (EEMCS)
Research Group:
Link to this item:http://purl.utwente.nl/publications/62062
Official URL:https://doi.org/10.1016/j.endm.2007.07.050
Export this item as:BibTeX
HTML Citation
Reference Manager


Repository Staff Only: item control page

Metis ID: 245869