An upper bound on the Ramsey number of trees (Q1821795)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 3999975
Language Label Description Also known as
default for all languages
No label defined
    English
    An upper bound on the Ramsey number of trees
    scientific article; zbMATH DE number 3999975

      Statements

      An upper bound on the Ramsey number of trees (English)
      0 references
      0 references
      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
      0 references
      0 references

      Identifiers