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

Abstract

top
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

How to cite

top

Pouria 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. [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. [2] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer-Verlag, New York, 2008). 
  3. [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. [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. [5] K. Markstr¨om, Extremal graphs for some problems on cycles in graphs, Congr. Numer. 171 (2004) 179-192. 
  6. [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. [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. [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 ?

top

You must be logged in to post comments.