On Ramsey numbers of sparse graphs

Alexandr Kostochka, Benny Sudakov

Research output: Contribution to journalArticlepeer-review


The Ramsey number, r(G), of a graph G is the minimum integer N such that, in every 2-colouring of the edges of the complete graph KN on N vertices, there is a monochromatic copy of G. In 1975, Burr and Erdos posed a problem on Ramsey numbers of d-degenerate graphs, i.e., graphs in which every subgraph has a vertex of degree at most d. They conjectured that for every d there exists a constant c(d) such that r(G) ≤ c(d)n for any d-degenerate graph G of order n. In this paper we prove that r(G) ≤n1+0(1) for each such G. In fact, we show that, for every ε > 0, sufficiently large n, and any graph H of order n1+ε, either H or its complement contains a (d, n)-common graph, that is, a graph in which every set of d vertices has at least n common neighbours. It is easy to see that any (d, n)-common graph contains every d-degenerate graph G of order n. We further show that, for every constant C, there is an n and a graph H of order Cn such that neither H nor its complement contains a (2, n)-common graph.

Original languageEnglish (US)
Pages (from-to)627-641
Number of pages15
JournalCombinatorics Probability and Computing
Issue number5-6 SPEC. ISS.
StatePublished - Sep 2003

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Statistics and Probability
  • Computational Theory and Mathematics
  • Applied Mathematics


Dive into the research topics of 'On Ramsey numbers of sparse graphs'. Together they form a unique fingerprint.

Cite this