Erdös-Gyárfás Conjecture on 2-power Cycle Lengths

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 K1,m-free graphs having minimum degree at least m+1 or maximum degree at least 2m-1.

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.

Back to Index Page Link to Glossary