András Gyárfás (born 1945) is a Hungarian

mathematician A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...

who specializes in the study of

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 ...

. He is famous for two conjectures: * Together with

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 ...

he conjectured what is now called the Erdős–Gyárfás conjecture which states that any

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 cycle 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^ ...

. * He and David Sumner independently formulated the

Gyárfás–Sumner conjecture In graph theory, the Gyárfás–Sumner conjecture asks whether, for every tree T and complete graph K, the graphs with neither T nor K as induced subgraphs can be properly colored using only a constant number of colors. Equivalently, it asks whet ...

according to which, for every

tree In botany, a tree is a perennial plant with an elongated stem, or trunk, usually supporting branches and leaves. In some usages, the definition of a tree may be narrower, e.g., including only woody plants with secondary growth, only ...

''T'', the ''T''-free graphs are

χ-bounded In graph theory, a \chi-bounded family \mathcal of graphs is one for which there is some function f such that, for every integer t the graphs in \mathcal with t=\omega(G) ( clique number) can be colored with at most f(t) colors. The function f(t) ...

. Gyárfás began working as a researcher for the Computer and Automation Research Institute of the Hungarian Academy of Sciences in 1968. He earned a candidate degree in 1980, and a doctorate (Dr. Math. Sci.) in 1992. He won the Géza Grünwald Commemorative Prize for young researchers of the János Bolyai Mathematical Society in 1978. He was co-author with Paul Erdős on 15 papers, and thus has Erdős number one.

References

External links

András Gyárfás
at the Computer and Automation Research Institute, Hungarian Academy of Sciences
Google scholar profile
20th-century Hungarian mathematicians 21st-century Hungarian mathematicians 1945 births Combinatorialists Living people {{Europe-mathematician-stub