Geodesic
On traceability and 2-factors in claw-free graphs
Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 1, pp. 55-71.

Voir la notice de l'article provenant de la source Library of Science

If G is a claw-free graph of sufficiently large order n, satisfying a degree condition σₖ > n + k² - 4k + 7 (where k is an arbitrary constant), then G has a 2-factor with at most k - 1 components. As a second main result, we present classes of graphs ₁,...,₈ such that every sufficiently large connected claw-free graph satisfying degree condition σ₆(k) > n + 19 (or, as a corollary, δ(G) > (n+19)/6) either belongs to ⋃ ⁸_i=1 _i or is traceable.
Keywords: traceability, 2-factor, claw, degree condition, closure 
@article{DMGT_2004_24_1_a4,
     author = {Fron\v{c}ek, Dalibor and Ryj\'a\v{c}ek, Zden\v{e}k and Skupie\'n, Zdzis{\l}aw},
     title = {On traceability and 2-factors in claw-free graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {55--71},
     publisher = {mathdoc},
     volume = {24},
     number = {1},
     year = {2004},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a4/}
}
TY  - JOUR
AU  - Fronček, Dalibor
AU  - Ryjáček, Zdeněk
AU  - Skupień, Zdzisław
TI  - On traceability and 2-factors in claw-free graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2004
SP  - 55
EP  - 71
VL  - 24
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a4/
LA  - en
ID  - DMGT_2004_24_1_a4
ER  - 
%0 Journal Article
%A Fronček, Dalibor
%A Ryjáček, Zdeněk
%A Skupień, Zdzisław
%T On traceability and 2-factors in claw-free graphs
%J Discussiones Mathematicae. Graph Theory
%D 2004
%P 55-71
%V 24
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a4/
%G en
%F DMGT_2004_24_1_a4
Fronček, Dalibor; Ryjáček, Zdeněk; Skupień, Zdzisław. On traceability and 2-factors in claw-free graphs. Discussiones Mathematicae. Graph Theory, Tome 24 (2004) no. 1, pp. 55-71. http://geodesic.mathdoc.fr/item/DMGT_2004_24_1_a4/

[1] J.A. Bondy and U.S.R. Murty, Graph Theory with applications (Macmillan, London and Elsevier, New York, 1976).

[2] V. Chvátal and P. Erdős, A note on hamiltonian circuits, Discrete Math. 2 (1972) 111-113, doi: 10.1016/0012-365X(72)90079-9.

[3] S. Brandt, O. Favaron and Z. Ryjáček, Closure and stable hamiltonian properties in claw-free graphs, J. Graph Theory 32 (2000) 30-41, doi: 10.1002/(SICI)1097-0118(200005)34:130::AID-JGT4>3.0.CO;2-R

[4] G.A. Dirac, In abstrakten Graphen vorhandene vollständige 4-Graphen und ihre Unterteilungen, Math. Nachr. 22 (1960) 61-85, doi: 10.1002/mana.19600220107.

[5] R. Faudree, O. Favaron, E. Flandrin, H. Li and Z.Liu, On 2-factors in claw-free graphs, Discrete Math. 206 (1999) 131-137, doi: 10.1016/S0012-365X(98)00398-7.

[6] O. Favaron, E. Flandrin, H. Li and Z. Ryjáček, Clique covering and degree conditions for hamiltonicity in claw-free graphs, Discrete Math. 236 (2001) 65-80, doi: 10.1016/S0012-365X(00)00432-5.

[7] R.L. Graham, M. Grötschel and L. Lovász, eds., (Handbook of Combinatorics. North-Holland, 1995).

[8] R. Gould and M. Jacobson, Two-factors with few cycles in claw-free graphs, preprint 1999.

[9] O. Kovárík, M. Mulac and Z. Ryjáček, A note on degree conditions for hamiltonicity in 2-connected claw-free graphs, Discrete Math. 244 (2002) 253-268, doi: 10.1016/S0012-365X(01)00088-7.

[10] H. Li, A note on hamiltonian claw-free graphs, Rapport de Recherche LRI No. 1022 (Univ. de Paris-Sud, 1996), submitted.

[11] F. Harary and C. St.J.A. Nash-Williams, On eulerian and hamiltonian graphs and line graphs, Canad. Math. Bull. 8 (1965) 701-709, doi: 10.4153/CMB-1965-051-3.

[12] Z. Ryjáček, On a closure concept in claw-free graphs, J. Combin. Theory (B) 70 (1997) 217-224, doi: 10.1006/jctb.1996.1732.

[13] Z. Ryjáček, A. Saito and R.H. Schelp, Closure, 2-factors and cycle coverings in claw-free graphs, J. Graph Theory 32 (1999) 109-117, doi: 10.1002/(SICI)1097-0118(199910)32:2109::AID-JGT1>3.0.CO;2-O