Premium
Multipartite Graph‐Tree Ramsey Numbers
Author(s) -
ERDÖS PAUL,
FAUDREE R. J.,
ROUSSEAU C. C.,
SCHELP R. H.
Publication year - 1989
Publication title -
annals of the new york academy of sciences
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.712
H-Index - 248
eISSN - 1749-6632
pISSN - 0077-8923
DOI - 10.1111/j.1749-6632.1989.tb16393.x
Subject(s) - memphis , annals , library science , state (computer science) , mathematics , computer science , history , classics , botany , algorithm , biology
Since it is known that r(K( m ) T) n for the large class of trees that have no vertices of large degree the upper and lower bounds are frequently identical In all cases these bounds are shown to differ by at most k For simple graphs F and G the Ramsey number r(F G) is the smallest integer p such that if the edges of the complete graph KP are colored red and blue either the red subgraph contains a copy of For the blue subgraph contains a copy of G If F is a graph with chromatic number X(F) then the chromatic surplus s(F) is the smallest number of vertices in a color class under any X(F) coloring of the vertices of F For any connected graph G of order n > s(F) the Ramsey number r(F G) satisfies the inequality