An upper bound on the Ramsey number of trees (Q1821795)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An upper bound on the Ramsey number of trees |
scientific article |
Statements
An upper bound on the Ramsey number of trees (English)
0 references
1987
0 references
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.
0 references
Ramsey number
0 references
monochromatic copy
0 references