Erdős–Gyárfás conjecture

From Wikipedia, the free encyclopedia

Markström's 24-vertex cubic planar graph with no 4- or 8-cycles, found in a computer search for counterexamples to the Erdős–Gyárfás conjecture. It has however cycles with 16 vertices.

In graph theory, the unproven Erdős–Gyárfás conjecture, made in 1995 by the prolific mathematician Paul Erdős and his collaborator András Gyárfás, states that any graph with minimum degree 3 contains a simple cycle whose length is a power of 2. Erdős offered a prize of $100 for proving the conjecture, or $50 for a counterexample.

It is known through computer searches of Gordon Royle and Klas Markström that any counterexample must have at least 17 vertices, and any cubic counterexample must have at least 30 vertices. Markström's searches found four graphs on 24 vertices in which the only power-of-two cycles have 16 vertices; one of these four graphs is planar.

[edit] See also

Conjectures of Erdős

[edit] References

Markström, Klas (2004). "Extremal graphs for some problems on cycles in graphs". Congr. Numerantium 171: 179–192.

Shauger, Stephen E. (1998). "Results on the Erdős–Gyárfás conjecture in K_1,m-free graphs". Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing: 61–65.

Daniel, Dale and Shauger, Stephen E. (2001). "A result on the Erdős–Gyárfás conjecture in planar graphs". Proc. 32nd Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing: 129–139.