The main treasure that Paul Erdős has left us is his collection of problems, most of which are still open today. These problems are seeds that Paul sowed and watered by giving numerous talks at meetings big and small, near and far. In the past, his problems have spawned many areas in graph theory and beyond (e.g., in number theory, probability, geometry, algorithms and complexity theory). Solutions or partial solutions to Erdős problems usually lead to further questions, often in new directions. These problems provide inspiration and serve as a common focus for all graph theorists. Through the problems, the legacy of Paul Erdős continues (particularly if solving one of these problems results in creating three new problems, for example.)
There is a huge literature of almost 1500 papers written by Erdős and his (more than 460) collaborators. Paul wrote many problem papers, some of which appeared in various (really hard-to-find) proceedings. Here is an attempt to collect and organize these problems in the area of graph theory. The list here is by no means complete or exhaustive. Our goal is to state the problems, locate the sources, and provide the references related to these problems. We will include the earliest and latest known references without covering the entire history of the problems because of space limitations (The most up-to-date list of Erdős' papers can be found in [65]; an electronic file is maintained by Jerry Grossman at [email protected].) There are many survey papers on the impact of Paul's work, e.g., see those in the books: A Tribute to Paul Erd ős [84], Combinatorics, Paul Erd ős is Eighty, Volumes 1 and 2 [83], and The Mathematics of Paul Erd ős, Volumes I and II [81].
To honestly follow the unique style of Paul Erdős, we will mention the fact that Erdős often offered monetary awards for solutions to a number of his favorite problems. In November 1996, a committee of Erdős' friends decided no more such awards will be given in Erdős' name. However, the author, with the help of Ron Graham, will honor future claims on the problems in this paper, provided the requirements previously set by Paul are satisfied (e.g., proofs have been verified and published in recognized journals).
Throughout this paper, the constants c, c , c 1 , c 2 , • • • and extremal functions f (n), f (n, k), f (n, k, r, t), g(n), • • • are used extensively, although within the context of each problem, the