Multicolor Ramsey Numbers for Paths and Cycles

Abstract

For given graphs G1;G2;:::;Gk;k ‚ 2, the multicolor Ramsey number R(G1;G2;:::;Gk) is the smallest integer n such that if we arbi- trarily color the edges of the complete graph on n vertices with k colors, then it is always a monochromatic copy of some Gi, for 1 • ik. We give a lower bound for k-color Ramsey number R(Cm;Cm;:::;Cm), where m ‚ 8 is even and Cm is the cycle on m vertices. In addition, we provide exact values for Ramsey numbers R(P3;Cm;Cp), where P3 is the path on 3 vertices, and several values for R(Pl;Pm;Cp), where l;m;p ‚ 2. In this paper we present new results in this fleld as well as some interesting conjectures.