# 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 (2014)

- Volume: 34, Issue: 3, page 635-640
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topPouria Salehi Nowbandegani, et al. "On the Erdős-Gyárfás Conjecture in Claw-Free Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 635-640. <http://eudml.org/doc/267999>.

@article{PouriaSalehiNowbandegani2014,

abstract = {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},

author = {Pouria Salehi Nowbandegani, Hossein Esfandiari, Mohammad Hassan Shirdareh Haghighi, Khodakhast Bibak},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {Erdős-Gyárfás conjecture; claw-free graphs; cycles},

language = {eng},

number = {3},

pages = {635-640},

title = {On the Erdős-Gyárfás Conjecture in Claw-Free Graphs},

url = {http://eudml.org/doc/267999},

volume = {34},

year = {2014},

}

TY - JOUR

AU - Pouria Salehi Nowbandegani

AU - Hossein Esfandiari

AU - Mohammad Hassan Shirdareh Haghighi

AU - Khodakhast Bibak

TI - On the Erdős-Gyárfás Conjecture in Claw-Free Graphs

JO - Discussiones Mathematicae Graph Theory

PY - 2014

VL - 34

IS - 3

SP - 635

EP - 640

AB - 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

LA - eng

KW - Erdős-Gyárfás conjecture; claw-free graphs; cycles

UR - http://eudml.org/doc/267999

ER -

## References

top- [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. Zbl1051.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. Zbl0997.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. Zbl0952.05038
- [8] J. Verstraëte, Unavoidable cycle lengths in graphs, J. Graph Theory 49 (2005) 151-167. doi:10.1002/jgt.20072[Crossref] Zbl1064.05091

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.