On the Erdős-Gyárfás conjecture in claw-free graphs

2011/09/25 by Pouria Salehi Nowbandegani, Hossein Esfandiari, Nowbandegani, Pouria Salehi +5
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO

paper · pdf · doi:10.48550/arxiv.1109.5398

Final version. Discussiones Mathematicae Graph Theory, to appear

arxiv created 2013/02/07 · arxiv updated 2013/02/08

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.

Related

• Erdős-Gyárfás conjecture on graphs without long induced paths
• Erdős-Gyárfás Conjecture for P₁₀-free Graphs
• Erdős-Gyárfás Conjecture for P₈-free graphs
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3
• Three Graphs and the Erdős-Gyárfás Conjecture