Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 794.05054
Autor: Erdös, Paul
Title: Some of my favorite solved and unsolved problems in graph theory. (In English)
Source: Quaest. Math. 16, No.3, 333-350 (1993).
Review: The new and old open problems and conjectures raised in this paper can be grouped in the following areas: I. Turán type problems in extremal graph theory. II. Problems on Ramsey numbers. III. Ramsey-Turán type problems. IV. Problems and results on (finite and infinite) chromatic numbers and chromatic critical graphs. V. Miscellaneous problems.
The greatest prize of 1,000 US dollars is offered by the author for a disproof of the equality limn ––> oo r(n)/n2n/2 = oo, where r(n) is the smallest integer for which every graph on r(n) vertices contains either a complete graph or an independent set on n vertices (but the author is sure that this equality holds, when the prize decreases to 100 US dollars only).
Reviewer: I.Tomescu (Bucuresti)
Classif.: * 05C35 Extremal problems (graph theory)
00A07 Problem books
05C15 Chromatic theory of graphs and maps
05C55 Generalized Ramsey theory
05C38 Paths and cycles
Keywords: Turán number; bipartite graph; extremal graph; Ramsey numbers; chromatic numbers; critical graphs
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag