Erdős–Gyárfás conjecture

Erdős–Gyárfás conjecture
Unsolved problems in mathematics
Must every cubic graph contain a simple cycle of length a power of two?
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 two. Erdős offered a prize of $100 for proving the conjecture, or $50 for a counterexample; it is one of many conjectures of Erdős.

If the conjecture is false, a counterexample would take the form of a graph with minimum degree three having no power-of-two cycles. 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.

Weaker results relating the degree of a graph to unavoidable sets of cycle lengths are known: there is a set S of lengths, with |S| = O(n0.99), such that every graph with average degree ten or more contains a cycle with its length in S (Verstraëte 2005), and every graph whose average degree is exponential in the iterated logarithm of n necessarily contains a cycle whose length is a power of two (Sudakov & Verstraëte 2008). The conjecture is also known to be true for planar claw-free graphs (Daniel & Shauger 2001) and for graphs that avoid large induced stars and satisfy additional constraints on their degrees (Shauger 1998).


  • Daniel, Dale; 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, pp. 129–139 .
  • 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 K1,m-free graphs", Proc. 29th Southeastern Int. Conf. Combinatorics, Graph Theory, and Computing, pp. 61–65 
  • Sudakov, Benny; Verstraëte, Jacques (2008), "Cycle lengths in sparse graphs", Combinatorica 28 (3): 357–372, arXiv:0707.2117, doi:10.1007/s00493-008-2300-6 .
  • Verstraëte, Jacques (2005), "Unavoidable cycle lengths in graphs", Journal of Graph Theory 49 (2): 151–167, doi:10.1002/jgt.20072 .

External links

Wikimedia Foundation. 2010.

Look at other dictionaries:

  • Erdős conjecture — The prolific mathematician Paul Erdős and his various collaborators made many famous mathematical conjectures, over a wide field of subjects.Some of these are the following: * The Cameron–Erdős conjecture on sum free sets of integers, solved by… …   Wikipedia

  • List of things named after Paul Erdős — The following were named after Paul Erdős:* Erdős number * Erdős cardinal * Erdős conjecture a list of numerous conjectures named after Erdős ** Erdős conjecture on arithmetic progressions ** Cameron–Erdős conjecture ** Erdős–Burr conjecture **… …   Wikipedia

  • András Gyárfás — (born 1945) is a Hungarian mathematician who specializes in combinatorics and graph theory. His Erdős number is 1. See also * Erdős–Gyárfás conjecture External links * [ András Gyárfás] at the Computer and… …   Wikipedia

  • Paul Erdős — at a student seminar in Budapest (fall 1992) Born 26 March 1913 …   Wikipedia

  • Liste de conjectures mathématiques — Ce qui suit est une liste de conjectures mathématiques, non exhaustive. Elles sont divisées en quatre sections, en accord avec leur état en 2011. Voir aussi : Conjecture d Erdős (en), qui liste des conjectures de Paul Erdős et de ses… …   Wikipédia en Français

  • Problèmes non résolus en mathématiques — Ce qui suit est une liste de problèmes non résolus en mathématiques. Sommaire 1 Problèmes du prix du millénaire 2 Autres problèmes encore non résolus 2.1 Théorie des nombres 2.2 …   Wikipédia en Français

  • List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

  • List of unsolved problems in mathematics — This article lists some unsolved problems in mathematics. See individual articles for details and sources. Contents 1 Millennium Prize Problems 2 Other still unsolved problems 2.1 Additive number theory …   Wikipedia

  • List of conjectures — This is an incomplete list of mathematical conjectures. They are divided into four sections, according to their status in 2007. See also: * Erdős conjecture, which lists conjectures of Paul Erdős and his collaborators * Unsolved problems in… …   Wikipedia

  • Liste Des Conjectures Mathématiques — Ce qui suit est une liste de conjectures mathématiques, contenues dans les pages de Wikipedia. Elles sont divisées en quatre sections, en accord avec leur état en 2006. Voir aussi : La conjecture d Erdős, qui liste les conjectures de Paul… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.