05565365

j

05565365 Gy\'arf\'as, Andr\'as S\'ark\"ozy, G\'abor N. Schelp, Richard H. Multipartite Ramsey numbers for odd cycles. J. Graph Theory 61, No. 1, 12-21 (2009). 2009 John Wiley \& Sons, New York, NY EN Ramsey numbers regularity lemma complete 5-partite graph monochromatic cycle

doi:10.1002/jgt.20364

The Ramsey number $r(C_n,C_n) = 2n - 1$ for $n$ odd. The authors conjecture the stronger result that if the edges of a complete $5$-partite graph $$ K_{\frac{n-1}{2},\frac{n-1}{2},\frac{n-1}{2},\frac{n-1}{2},1} $$ are $2$-colored, then there will be a monochromatic $C_n$. Thus, deleting the edges from $4$ vertex disjoint copies of a $K_{(n-1)/2}$ from the complete graph $K_{2n - 1}$ will still result in a monochromatic $C_n$. They show that if the edges from a $K_{(n+1)/1}$ are deleted from a $K_{2n-1}$, then there is a $2$-coloring without a monochromatic $C_n$. To support the conjecture they show that for any $\epsilon > 0$ and $n$ sufficiently large, any $2$-edge coloring of a complete $5$-partite graph $K_{m_1,m_2,m_3,m_4,m_5}$ with $\epsilon n \leq m_1 \leq m_2 \leq m_3 \leq m_4 \leq m_5 \leq n/2$ and $m_1 + m_2 + m_3 + m_4 + m_5 = (2 + \epsilon)n$ will contain a monochromatic $C_n$. Ralph Faudree (Memphis)