In this paper we study three-color Ramsey numbers. Let Ki,j denote a complete i by j bipartite graph. We shall show that (i) for any connected graphs G1, G2 and G3, if r(G 1, G2) ≥ s(G3), then r(G1, G 2, G3) ≥ (r(G1, G2) - 1)(χ(G3) - 1) + s(G3), where s(G3) is the chromatic surplus of G3; (ii) (k + m - 2) (n - 1) + 1 ≤ r(K 1,k, K1,m, Kn) ≤ (k + m - 1)(n - 1) + 1, and if k or m is odd, the second inequality becomes an equality; (iii) for any fixed m ≥ k ≥ 2, there is a constant c such that r(Kk,m, K k,m, Kn) ≤ c(n/log n)k, and r(C 2m, C2m, Kn) ≤ c(n/log n)m/(m-1) for sufficiently large n.
Scopus Subject Areas
- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Monochromatic graph
- Three-color Ramsey number