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
topHow 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 ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.