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
Fingerprint
Dive into the research topics of 'On graphs with small ramsey numbers'. Together they form a unique fingerprint.Cite this
- APA
- Standard
- Harvard
- Vancouver
- Author
- BIBTEX
- RIS