The Erdös–Gyárfás conjecture
Search
Subjects
- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)
About Erdös
About This Site
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. |