PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
2014 | 34 | 3 | 635-640
Tytuł artykułu

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

Treść / Zawartość
Warianty tytułu
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
Wydawca
Rocznik
Tom
34
Numer
3
Strony
635-640
Opis fizyczny
Daty
wydano
2014-08-01
poprawiono
2012-02-06
otrzymano
2012-08-29
zaakceptowano
2013-02-06
online
2014-07-16
Twórcy
  • Department of Combinatorics and Optimization University of Waterloo Waterloo, Ontario, Canada N2L 3G1, pouria.salehi@gmail.com
  • Department of Computer Science University of Maryland College Park College Park, MD 20742, USA, shirdareh@susc.ac.ir
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]
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_7151_dmgt_1732
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.