Subdivided graphs have linear ramsey numbers

Research output: Contribution to journalArticlepeer-review

21 Scopus citations

Abstract

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
Volume18
Issue number4
DOIs
StatePublished - Jul 1994
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Geometry and Topology

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

Cite this