RAMSEY-TYPE RESULTS FOR TREES VERSUS NEAR-COMPLETE GRAPHS

For given graphs G۱, G۲ and G, by G → (G۱, G۲) we mean if the edges of G are arbitrarily colored by red and blue, then there is either a red monochromatic copy of G₁ or a blue monochromatic copy of G۲ in G. The Ramsey number R(G۱, G۲) is defined as the smallest positive integer n such that Kn → (G۱, G۲). Let Tm is any tree of order m ≥ ۳ and G is any graph of order n ≥ ۴ having clique number n ۱. In this note, we prove that if R(Tm,G) = (m − ۱)(n − ۲) + ۱ and H is a subgraph of Kr such that H → (Tm, G), then ۸(H) ≥ (m − ۱)(n − ۳) + ۱.

کلیدواژه ها:

Ramsey number ، Tree ، Near-complete graph