The Ramsey number of a graph with bounded maximum degree (Q798674): Difference between revisions

\textit{S. Burr} and \textit{P. Erdős} [Infinite finite Sets, Colloq. Honour Paul Erdős, Keszthely 1973, Colloq. Math. Soc. János Bolyai 10, 215- 240 (1975; Zbl 0316.05110)] conjectured that the Ramsey number of a graph of bounded degree grows linearly with the number of vertices of the graph. This conjecture was confirmed by the authors. More precisely, they proved the following: Theorem: For each positive integer d, there exists a constant c depending only on d, such that the Ramsey number \(r(G)\leq cn\) for any graph G on n vertices with maximum degree d. A powerful tool used in the proof is the ''regularity'' lemma of \textit{E. Szemerédi} [Problèmes combinatoires et théorie des graphes, Orsay 1976, Colloq. Int. CNRS, No.260, 399-401 (1978; Zbl 0413.05055)].