1994/07/01 by Noga Alon · 1 citation
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics #Ramsey's theorem #Mathematics #Subdivision #Vertex (graph theory) #Graph #Wheel graph #Discrete mathematics #Graph power #Line graph
paper · doi:10.1002/jgt.3190180406
openalex publication_date 1994/07/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
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 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.