{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,25]],"date-time":"2025-09-25T18:08:10Z","timestamp":1758823690559},"reference-count":0,"publisher":"Cambridge University Press (CUP)","issue":"5-6","license":[{"start":{"date-parts":[[2003,12,3]],"date-time":"2003-12-03T00:00:00Z","timestamp":1070409600000},"content-version":"unspecified","delay-in-days":32,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2003,11]]},"abstract":"<jats:p>The <jats:italic>Ramsey number<\/jats:italic>, <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline1.png\" \/>, of a graph <jats:italic>G<\/jats:italic> is the minimum integer <jats:italic>N<\/jats:italic> such that, in every 2-colouring of the edges of the complete graph <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline2.png\" \/> on <jats:italic>N<\/jats:italic> vertices, there is a monochromatic copy of <jats:italic>G<\/jats:italic>. In 1975, Burr and Erd\u0151s posed a problem on Ramsey numbers of <jats:italic>d<\/jats:italic>-<jats:italic>degenerate<\/jats:italic> graphs, <jats:italic>i.e.<\/jats:italic>, graphs in which every subgraph has a vertex of degree at most <jats:italic>d<\/jats:italic>. They conjectured that for every <jats:italic>d<\/jats:italic> there exists a constant <jats:italic>c(d)<\/jats:italic> such that <jats:disp-formula><jats:graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" position=\"float\" xlink:href=\"S0963548303005728_equ1.png\" \/><\/jats:disp-formula> for any <jats:italic>d<\/jats:italic>-degenerate graph <jats:italic>G<\/jats:italic> of order <jats:italic>n<\/jats:italic>.<\/jats:p><jats:p>In this paper we prove that <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline3.png\" \/> for each such <jats:italic>G<\/jats:italic>. In fact, we show that, for every <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline4.png\" \/>, sufficiently large <jats:italic>n<\/jats:italic>, and any graph <jats:italic>H<\/jats:italic> of order <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline5.png\" \/>, either <jats:italic>H<\/jats:italic> or its complement contains a <jats:italic>(d,n)<\/jats:italic>-<jats:italic>common<\/jats:italic> graph, that is, a graph in which every set of <jats:italic>d<\/jats:italic> vertices has at least <jats:italic>n<\/jats:italic> common neighbours. It is easy to see that any <jats:italic>(d,n)<\/jats:italic>-common graph contains every <jats:italic>d<\/jats:italic>-degenerate graph <jats:italic>G<\/jats:italic> of order <jats:italic>n<\/jats:italic>. We further show that, for every constant <jats:italic>C<\/jats:italic>, there is an <jats:italic>n<\/jats:italic> and a graph <jats:italic>H<\/jats:italic> of order <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline6.png\" \/> such that neither <jats:italic>H<\/jats:italic> nor its complement contains a <jats:inline-graphic xmlns:xlink=\"http:\/\/www.w3.org\/1999\/xlink\" mime-subtype=\"png\" mimetype=\"image\" xlink:href=\"S0963548303005728_inline7.png\" \/>-common graph.<\/jats:p>","DOI":"10.1017\/s0963548303005728","type":"journal-article","created":{"date-parts":[[2003,12,3]],"date-time":"2003-12-03T14:23:14Z","timestamp":1070461394000},"page":"627-641","source":"Crossref","is-referenced-by-count":22,"title":["On Ramsey Numbers of Sparse Graphs"],"prefix":"10.1017","volume":"12","author":[{"given":"Alexander","family":"Kostochka","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"B","family":"Sudakov","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2003,12,3]]},"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548303005728","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T09:22:51Z","timestamp":1589534571000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548303005728\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,11]]},"references-count":0,"journal-issue":{"issue":"5-6","published-print":{"date-parts":[[2003,11]]}},"alternative-id":["S0963548303005728"],"URL":"https:\/\/doi.org\/10.1017\/s0963548303005728","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,11]]}}}