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

• Autorzy: Pouria Salehi Nowbandegani , Hossein Esfandiari , Mohammad Hassan Shirdareh Haghighi , Khodakhast Bibak
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

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

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 635-640

Daty

wydano

2014-08-01

poprawiono

2012-02-06

otrzymano

2012-08-29

zaakceptowano

2013-02-06

online

2014-07-16

Twórcy

autor

Pouria Salehi Nowbandegani

• Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario, Canada N2L 3G1

autor

Hossein Esfandiari

• Department of Mathematics Shiraz University Shiraz 71454, Iran

autor

Mohammad Hassan Shirdareh Haghighi

• Department of Computer Science University of Maryland College Park College Park, MD 20742, USA

autor

Khodakhast Bibak

• Department of Mathematics Shiraz University Shiraz 71454, Iran

Bibliografia

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

Identyfikatory

DOI

10.7151/dmgt.1732