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
    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