Multicolor Ramsey number for even cycles
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
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 multicolored Ramsey problem for even cycles (proposed by Erdös and Graham [2])
Determine \(r(\underbrace{C_{2m}, \ldots, C_{2m}}_k)\).
It was proved [1] that
\begin{eqnarray*}
r(\underbrace{C_4, \ldots, C_4}_k)& \leq& k^2 + k +1 \mbox{~~~for all \(k\)}
r(\underbrace{C_4, \ldots, C_4}_k)& >& k^2  k +1 \mbox{~~~for prime power \(k\)}.
\end{eqnarray*}
The following upper and lower bounds for \( r(\underbrace{C_{2m}, \ldots, C_{2m}}_k)\) were given in [2]:
\(\displaystyle c k^{1+1/2m} \leq r(\underbrace{C_{2m}, \ldots, C_{2m}}_k) \leq c' k^{1+1/(m1)}. \)
The lower bound can be further improved by using results in [3]:
\(\displaystyle r(\underbrace{C_{2m}, \ldots, C_{2m}}_k) \geq c'' (\frac k {\log k})^{1+ 2/(3m5)}. \)
Bibliography  

1  F. R. K. Chung and R. L. Graham. On multicolor Ramsey numbers for complete bipartite graphs, J. Comb. Th. (B) 18 (1975), 16469.

2 
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,
917, Springer, BerlinNew York, 1981.

3  F. Lazebnik, V. A. Ustimenko and A. J. Woldar,
A new series of dense graphs of high girth, Bull. Amer.
Math. Soc. 32 (1995), 7379.
