On the Erdős-Gyárfás Conjecture in Claw-Free Graphs
Pouria Salehi Nowbandegani ; Hossein Esfandiari ; Mohammad Hassan Shirdareh Haghighi ; Khodakhast Bibak
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 635-640 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:267999 
@article{bwmeta1.element.doi-10_7151_dmgt_1732,
     author = {Pouria Salehi Nowbandegani and Hossein Esfandiari and Mohammad Hassan Shirdareh Haghighi and Khodakhast Bibak},
     title = {On the Erd\H os-Gy\'arf\'as Conjecture in Claw-Free Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {635-640},
     zbl = {1295.05135},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1732}
}

Pouria Salehi Nowbandegani; Hossein Esfandiari; Mohammad Hassan Shirdareh Haghighi; Khodakhast Bibak. On the Erdős-Gyárfás Conjecture in Claw-Free Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 635-640. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1732/

[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. | Zbl 1051.05051

[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. | Zbl 0997.05053

[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[Crossref]

[5] K. Markstr¨om, 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¸eba, Poland.

[7] S.E. Shauger, Results on the Erdős-Gyárfás conjecture in K1,m-free graphs, Congr. Numer. 134 (1998) 61-65. | Zbl 0952.05038

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