On some three-color Ramsey numbers

Wai Chee SHIU*, Peter Che Bor Lam, Yusheng Li

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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.

Original languageEnglish
Pages (from-to)249-258
Number of pages10
JournalGraphs and Combinatorics
Volume19
Issue number2
DOIs
Publication statusPublished - 2003

Scopus Subject Areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

User-Defined Keywords

  • Monochromatic graph
  • Three-color Ramsey number

Fingerprint

Dive into the research topics of 'On some three-color Ramsey numbers'. Together they form a unique fingerprint.

Cite this