Erdös' Problems on Graphs

Paul Erdös has been described as a "prince of problem solvers and the absolute monarch of problem posers." This is a testament to both his legacy of over 1500 publications and his numerous proposed problems, many of which are still open today. Throughout his career, work on his proposed problems in a variety of areas of mathematics consistently led to advances and discoveries. Much of Erdös' legacy stems from his ability to capture the essence of a deep mathematical issue in a seemingly simple problem. Perhaps the best explanation can be paraphrased as follows:

Problems have always been an essential part of my mathematical life. A well chosen problem can isolate an essential difficulty in a particular area, serving as a benchmark against which progress in this area can be measured. An innocent looking problem often gives no hint as to its true nature. It might be like a 'marshmallow,' serving as a tasty tidbit supplying a few moments of fleeting enjoyment. Or it might be like an 'acorn,' requiring deep and subtle new insights from which a mighty oak can develop [....] In this note I would like to describe a variety of my problems which I would classify as my favorites. Of course, I can't guarantee that they are all 'acorns' but because many have thwarted the efforts of best mathematicians for many decades (and have often acquired a cash reward for their solutions), it may indicate that new ideas will be needed, which can in turn, lead to more general results, and naturally, to further new problems. In this way, the cycle of life in mathematics continues forever.
- "Some of my favorite problems and results" by Paul Erdös

There have been several surveys collecting some of Erdös' open problems, the most extensive being "Erdös on Graphs: His Legacy of Unsolved Problems" by Fan Chung and Ron Graham, published in 1998. This website is intended to be a "living version" of this work, one that will be updated and expanded upon as progress is made on these problems. Though Erdös' interests ranged across many branches of mathematics, this site will focus on open problems in graph theory. The goal is to provide a history of each problem, along with progress, references, and for some problems the cash prize offered for a solution. Our hope is that this will facilitate new interest, progress, and discussion on these and other open problems.

A watercolor of Erdös by Fan Chung.
If you have any updates on the progress of one of the problems here, spot an error, or have any other comments/concerns please feel free to send a note to erdosproblems@math.ucsd.edu