Premium
Subdivided graphs have linear ramsey numbers
Author(s) -
Alon Noga
Publication year - 1994
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190180406
Subject(s) - combinatorics , ramsey's theorem , mathematics , subdivision , vertex (graph theory) , graph , wheel graph , discrete mathematics , graph power , line graph , archaeology , history
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 12 n . 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.