An upper bound on the Ramsey number of trees
type: Item
instance of: scholarly article
title: An upper bound on the Ramsey number of trees
zbMATH Open document ID: 0617.05048
DOI: 10.1016/0012-365X(87)90107-5
author: Zsolt Tuza
author: András Gyárfás
published in: Discrete Mathematics
publication date: 1987-01-01T00:00:00Z
review text: Let f(k,n) denote the smallest integer m so that, if the edges of the complete graph on m vertices are colored with k colors, then there exists a monochromatic subgraph with minimum degree at least n. Given a graph G, the Ramsey number r(G,k) is the smallest integer m so that every k- coloring of the edges of the complete graph on m vertices yields a monochromatic copy of G. The author proves: Theorem. \(f(k,n)\leq (n- 1)(k+\sqrt{k(k-1)})+2;\) which gives: Corollary. \(r(T_ n,k)\leq (n- 1)(k+\sqrt{k(k-1)})+2;\) where \(T_ n\) is any tree on n vertices.
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C05
zbMATH DE Number: 3999975
zbMATH Keywords: Ramsey number
zbMATH Keywords: monochromatic copy
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: Q3852212
cites work: Q4087229
description: scientific article; zbMATH DE number 3999975