graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, the unproven Erdős–Gyárfás conjecture, made in 1995 by mathematician

Paul Erdős Paul Erdős ( ; 26March 191320September 1996) was a Hungarian mathematician. He was one of the most prolific mathematicians and producers of mathematical conjectures of the 20th century. pursued and proposed problems in discrete mathematics, g ...

and his collaborator

András Gyárfás András Gyárfás (born 1945) is a Hungarian mathematician who specializes in the study of graph theory. He is famous for two conjectures: * Together with Paul Erdős he conjectured what is now called the Erdős–Gyárfás conjecture which sta ...

, states that every

graph Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties *Graph (topology), a topological space resembling a graph in the sense of discret ...

with minimum degree 3 contains a

simple cycle In graph theory, a cycle in a graph is a non-empty trail in which only the first and last vertices are equal. A directed cycle in a directed graph is a non-empty directed trail in which only the first and last vertices are equal. A graph with ...

whose length is a

power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number 2, two as the Base (exponentiation), base and integer as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...

. 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 Gordon F. Royle is a professor at the School of Mathematics and Statistics at The University of Western Australia. Royle is the co-author (with Chris Godsil) of the book ''Algebraic Graph Theory'' (Springer Verlag, 2001, ). Royle is also known ...

and Klas Markström that any counterexample must have at least 17 vertices, and any

cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...

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; however, the Erdős–Gyárfás conjecture is now known to be true for the special case of 3-connected cubic planar graphs 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(''n''^0.99), such that every graph with average degree ten or more contains a cycle with its length in ''S'' , 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 . The conjecture is also known to be true for planar

claw-free graph In graph theory, an area of mathematics, a claw-free graph is a graph that does not have a claw (graph theory), claw as an induced subgraph. A claw is another name for the complete bipartite graph K_ (that is, a star graph comprising three edges, ...

s and for graphs that avoid large induced

star A star is a luminous spheroid of plasma (physics), plasma held together by Self-gravitation, self-gravity. The List of nearest stars and brown dwarfs, nearest star to Earth is the Sun. Many other stars are visible to the naked eye at night sk ...

s and satisfy additional constraints on their degrees .

References

*. *. *. * *. *.

External links

*Exoo, Geoffrey
Graphs Without Cycles of Specified Lengths
*West, Douglas B.

' {{DEFAULTSORT:Erdos-Gyarfas conjecture Conjectures Unsolved problems in graph theory Gyarfas conjecture