Multipartite Ramsey numbers for odd cycles

In this paper we study multipartite Ramsey numbers for odd cycles. We formulate the following conjecture: Let n ≥5 be an arbitrary positive odd integer; then, in any two‐coloring of the edges of the complete 5‐partite graph K (( n −1)/2, ( n −1)/2, ( n −1)/2, ( n −1)/2, 1) there is a monochromatic C n , a cycle of length n . This roughly says that the Ramsey number for C n (i.e. 2 n −1 ) will not change (somewhat surprisingly) if four large “holes” are allowed. Note that this would be best possible as the statement is not true if we delete from K 2 n −1 the edges within a set of size ( n + 1)/2. We prove an approximate version of the above conjecture. © 2009 Wiley Periodicals, Inc. J Graph Theory 61:12‐21, 2009