**Originator(s):**
Paul Erdös and András Gyárfás

**Conjecture:**
Every graph with minimum degree 3 has a cycle whose length is a power of 2.
(Yair Caro suggests the weaker question of whether every such graph has
a cycle whose length is a non-trivial power of some natural number.)

**Comments/Partial results:**
Daniel and Shauger [DS] proved the conjecture for planar claw-free graphs.
Shauger [S] also proved it for *K _{1,m}*-free graphs having
minimum degree at least

**References:**

[DS] Daniel, D.; Shauger, S. E.
A result on the Erdös-Gyárfás conjecture in planar graphs.
Proceedings of the Thirty-second Southeastern International Conference on
Combinatorics, Graph Theory and Computing (Baton Rouge, LA, 2001).
Congr. Numer. 153 (2001), 129--139.

[S] Shauger, S. E.
Results on the Erdös-Gyárfás conjecture in $K\sb {1,m}$-free graphs.
Proceedings of the Twenty-ninth Southeastern International Conference on
Combinatorics, Graph Theory and Computing (Boca Raton, FL, 1998).
Congr. Numer. 134 (1998), 61--65.