TY - JOUR
T1 - On some three-color Ramsey numbers
AU - Shiu, Wai Chee
AU - Lam, Peter Che Bor
AU - Li, Yusheng
N1 - Copyright:
Copyright 2020 Elsevier B.V., All rights reserved.
PY - 2003/6
Y1 - 2003/6
N2 - 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.
AB - 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.
KW - Monochromatic graph
KW - Three-color Ramsey number
UR - http://www.scopus.com/inward/record.url?scp=0042853331&partnerID=8YFLogxK
U2 - 10.1007/s00373-002-0495-7
DO - 10.1007/s00373-002-0495-7
M3 - Journal article
AN - SCOPUS:0042853331
SN - 0911-0119
VL - 19
SP - 249
EP - 258
JO - Graphs and Combinatorics
JF - Graphs and Combinatorics
IS - 2
ER -