\(3\)-color Ramsey number for \(n\)-cycles

For graphs \( G_i\), \( i=1,\dots,k\), let \( r(G_1,\dots,G_k)\) denote the smallest integer \( m\) satisfying the property that if the edges of the complete graph \( K_m\) are colored in \( k\) colors, then for some \( i\), \( 1\leq i\leq k\), there is a subgraph isomorphic to \( G_i\) with all edges in the \( i\)-th color.

A problem on three cycles (proposed by Bondy and Erdös[1])

Show that \[ r(C_n,C_n,C_n) \leq 4n-3. \]

For odd \( n\), if the above inequality is true, it is the best possible. Recently, Łuczak (personal communication) has shown that \( r(C_n,C_n,C_n) \leq 4n + o(n)\).

1 P. Erdös, Some new problems and results in graph theory and other branches of combinatorial mathematics, Combinatorics and graph theory (Calcutta, 1980), Lecture Notes in Math., 885, 9-17, Springer, Berlin-New York, 1981.