Premium
On graphs with small Ramsey numbers *
Author(s) -
Kostochka A. V.,
Rödl V.
Publication year - 2001
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.1014
Subject(s) - combinatorics , mathematics , ramsey's theorem , bipartite graph , graph , integer (computer science) , degree (music) , monochromatic color , discrete mathematics , induced subgraph , vertex (graph theory) , physics , computer science , acoustics , programming language , optics
Abstract Let R ( G ) denote the minimum integer N such that for every bicoloring of the edges of K N , at least one of the monochromatic subgraphs contains G as a subgraph. We show that for every positive integer d and each γ,0 < γ < 1, there exists k = k ( d ,γ) such that for every bipartite graph G = ( W , U ; E ) with the maximum degree of vertices in W at most d and $|U|\leq |W|^{\gamma }$ , $R(G)\leq k|W|$ . This answers a question of Trotter. We give also a weaker bound on the Ramsey numbers of graphs whose set of vertices of degree at least d + 1 is independent. © 2001 John Wiley & Sons, Inc. J Graph Theory 37: 198–204, 2001