Around a conjecture of Erdos in graph Ramsey theory

Abstract

For given graphs G1 and G2 the Ramsey number R(G1;G2), is the smallest positive integer n such that each blue-red edge coloring of the complete graph Kn contains a blue copy of G1 or a red copy of G2. In 1983, Erd}os conjectured that there is an absolute constant c such that R(G) = R(G;G) 2c p m for any graph G with m edges and no isolated vertices. Recently this conjecture was proved by Sudakov. In this short note, we give an extention of this result. As a corollary of our result we have R(G1;G2) 2250 p m for graphs G1 and G2 with no isolated vertices and m1 and m2 edges, respectively, where m = fm1;m2g Keywords: Ramsey number, Erd}os' conjecrure.

Keywords

• ramsey number
• diagonal rmsey number
• erdos' conjecrure