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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom