On graphs with small ramsey numbers

A. V. Kostochka, V. Rödl

Research output: Contribution to journalArticlepeer-review

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 languageEnglish (US)
Pages (from-to)198-204
Number of pages7
JournalJournal of Graph Theory
Volume37
Issue number4
DOIs
StatePublished - 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