Geodesic
On the Erdős-Gyárfás conjecture in claw-free graphs
Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 635-640.

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

The Erdős-Gyárfás conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. Since this conjecture has proven to be far from reach, Hobbs asked if the Erdős-Gyárfás conjecture holds in claw-free graphs. In this paper, we obtain some results on this question, in particular for cubic claw-free graphs.
Keywords: Erdős-Gyárfás conjecture, claw-free graphs, cycles 
@article{DMGT_2014_34_3_a16,
     author = {Nowbandegani, Pouria Salehi and Esfandiari, Hossein and Haghighi, Mohammad Hassan Shirdareh and Bibak, Khodakhast},
     title = {On the {Erd\H{o}s-Gy\'arf\'as} conjecture in claw-free graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {635--640},
     publisher = {mathdoc},
     volume = {34},
     number = {3},
     year = {2014},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a16/}
}
TY  - JOUR
AU  - Nowbandegani, Pouria Salehi
AU  - Esfandiari, Hossein
AU  - Haghighi, Mohammad Hassan Shirdareh
AU  - Bibak, Khodakhast
TI  - On the Erdős-Gyárfás conjecture in claw-free graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2014
SP  - 635
EP  - 640
VL  - 34
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a16/
LA  - en
ID  - DMGT_2014_34_3_a16
ER  - 
%0 Journal Article
%A Nowbandegani, Pouria Salehi
%A Esfandiari, Hossein
%A Haghighi, Mohammad Hassan Shirdareh
%A Bibak, Khodakhast
%T On the Erdős-Gyárfás conjecture in claw-free graphs
%J Discussiones Mathematicae. Graph Theory
%D 2014
%P 635-640
%V 34
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a16/
%G en
%F DMGT_2014_34_3_a16
Nowbandegani, Pouria Salehi; Esfandiari, Hossein; Haghighi, Mohammad Hassan Shirdareh; Bibak, Khodakhast. On the Erdős-Gyárfás conjecture in claw-free graphs. Discussiones Mathematicae. Graph Theory, Tome 34 (2014) no. 3, pp. 635-640. http://geodesic.mathdoc.fr/item/DMGT_2014_34_3_a16/

[1] J.A. Bondy, Extremal problems of Paul Erdős on circuits in graphs, in: Paul Erdős and his Mathematics, II, Bolyai Soc. Math. Stud., 11, Janos Bolyai Math. Soc., Budapest (2002), 135-156.

[2] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, New York, 2008).

[3] D. Daniel and S.E. Shauger, A result on the Erdős-Gyárfás conjecture in planar graphs, Congr. Numer. 153 (2001) 129-140.

[4] P. Erdős, Some old and new problems in various branches of combinatorics, Discrete Math. 165/166 (1997) 227-231. doi:10.1016/S0012-365X(96)00173-2

[5] K. Markström, Extremal graphs for some problems on cycles in graphs, Congr. Numer. 171 (2004) 179-192.

[6] P. Salehi Nowbandegani and H. Esfandiari, An experimental result on the Erdős-Gyárfás conjecture in bipartite graphs, 14th Workshop on Graph Theory CID, September 18-23, 2011, Szklarska Poręba, Poland.

[7] S.E. Shauger, Results on the Erdős-Gyárfás conjecture in $K_{1,m}$-free graphs, Congr. Numer. 134 (1998) 61-65.

[8] J. Verstraëte, Unavoidable cycle lengths in graphs, J. Graph Theory 49 (2005) 151-167. doi:10.1002/jgt.20072