The Ramsey number of a graph with bounded maximum degree (Q798674)

From MaRDI portal
Revision as of 12:56, 14 June 2024 by ReferenceBot (talk | contribs) (‎Changed an Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
The Ramsey number of a graph with bounded maximum degree
scientific article

    Statements

    The Ramsey number of a graph with bounded maximum degree (English)
    0 references
    0 references
    0 references
    0 references
    1983
    0 references
    \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)].
    0 references
    Ramsey number
    0 references
    bounded degree
    0 references
    0 references
    0 references
    0 references

    Identifiers