Subdivided graphs have linear ramsey numbers

Research output: Contribution to journalArticlepeer-review

28 Scopus citations


It is shown that the Ramsey number of any graph with n vertices in which no two vertices of degree at least 3 are adjacent is at most 12n. In particular, the above estimate holds for the Ramsey number of any n‐vertex subdivision of an arbitrary graph, provided each edge of the original graph is subdivided at least once. This settles a problem of Burr and Erdös.

Original languageEnglish (US)
Pages (from-to)343-347
Number of pages5
JournalJournal of Graph Theory
Issue number4
StatePublished - Jul 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology


Dive into the research topics of 'Subdivided graphs have linear ramsey numbers'. Together they form a unique fingerprint.

Cite this