Abstract
| Original language | Undefined |
|---|---|
| Article number | 10.1007/s00373-009-0855-7 |
| Pages (from-to) | 427-460 |
| Number of pages | 34 |
| Journal | Graphs and combinatorics |
| Volume | 25 |
| Issue number | 4 |
| DOIs | |
| Publication status | Published - 2009 |
Keywords
- EWI-17516
- IR-70041
- METIS-265816
Cite this
}
Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs. / Broersma, Haitze J.; Paulusma, Daniël; Yoshimoto, Kiyoshi.
In: Graphs and combinatorics, Vol. 25, No. 4, 10.1007/s00373-009-0855-7, 2009, p. 427-460.Research output: Contribution to journal › Article › Academic › peer-review
TY - JOUR
T1 - Sharp upper bounds on the minimum number of components of 2-factors in claw-free graphs
AU - Broersma, Haitze J.
AU - Paulusma, Daniël
AU - Yoshimoto, Kiyoshi
N1 - 10.1007/s00373-009-0855-7
PY - 2009
Y1 - 2009
N2 - Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 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 $\delta - 1$ by $\delta$, respectively.
AB - Let $G$ be a claw-free graph with order $n$ and minimum degree $\delta$. We improve results of Faudree et al. and Gould & Jacobson, and solve two open problems by proving the following two results. 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 $\delts \ge 5$, then $G$ has a 2-factor with at most $(n - 3)/(\delta - 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 $\delta - 1$ by $\delta$, respectively.
KW - EWI-17516
KW - IR-70041
KW - METIS-265816
U2 - 10.1007/s00373-009-0855-7
DO - 10.1007/s00373-009-0855-7
M3 - Article
VL - 25
SP - 427
EP - 460
JO - Graphs and combinatorics
JF - Graphs and combinatorics
SN - 0911-0119
IS - 4
M1 - 10.1007/s00373-009-0855-7
ER -