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 |U| ≤ |W|γ, R(G)≤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.
Original language | English (US) |
---|---|
Pages (from-to) | 198-204 |
Number of pages | 7 |
Journal | Journal of Graph Theory |
Volume | 37 |
Issue number | 4 |
DOIs | |
State | Published - Aug 2001 |
Keywords
- Bipartite graphs
- Ramsey numbers
ASJC Scopus subject areas
- Geometry and Topology