The Erdös–Gyárfás conjecture

The Erdös–Gyárfás conjecture ($100 for proof, $50 for counterexample)

Any graph with minimum degree \(3\) contains a simple cycle whose length is a power of \(2\).

Royle and Markström showed through computer search that any counterexample contains more than 17 vertices, and moreover any cubic counterexample must contain more than 30 vertices [2].

The conjecture is known to be true for certain families of graphs. In 1998, Shauger showed it holds for graphs that avoid large induced stars and satisfy some degree contraints [1]. In 2001, Daniel and Shauger proved the conjecture holds for planar claw free graphs [3].

There are several related, yet weaker, results concerning unavoidable cycle lengths. In 2005, Verstraëte showed there is a set \(S\) of lengths, with \(|S| = O(n^{0.99})\), such that every graph with average degree \(10\) or more contains a cycle with its length in \(S\) [5]. In 2008, Sudakov and Verstraëte showed the conjecture holds for every graph whose average degree is in the iterated logarithm of the number of vertices [4].

Bibliography
1 D. Daniel and S. Shauger, A result on the Erdos–Gyárfás conjecture in planar graphs, Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing (2001), 129–139.
2 K. Markström, Extremal graphs for some problems on cycles in graphs, Congr. Numerantium 171 (2004), 179–192.
3 S. Shauger, Results on the Erdos–Gyárfás conjecture in K1,m-free graphs, Proc. 29th Southeastern Int. Conf. Combinatorics Graph Theory, and Computing 171 (1998), 61–65.
4 B. Sudakov and J. Verstraëte. Cycle lengths in sparse graphs, Combinatorica 28 (2008), 357–372.
5 J. Verstraëte. Unavoidable cycle lengths in graphs, Journal of Graph Theory 49 (2005), 151–167.