On graphs with small Ramsey numbers* |
| |
Authors: | A V Kostochka V Rdl |
| |
Institution: | A. V. Kostochka,V. Rödl |
| |
Abstract: | Let R(G) denote the minimum integer N such that for every bicoloring of the edges of KN, 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 , . 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 |
| |
Keywords: | Ramsey numbers bipartite graphs |
|
|