\documentclass[12pt]{article} \usepackage{e-jc,amsmath} \specs{P3.53}{23(3)}{2016} \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} %\documentstyle[12pt]{article} %\textheight 8in\textwidth 6in\oddsidemargin 0in\evensidemargin 0in \newtheorem{theorem}{Theorem}\newtheorem{lemma}{Lemma} \newtheorem{corollary}{Corollary} \newtheorem{claim}{Claim} \newtheorem{fact}{Fact}\newtheorem{conjecture}{Conjecture} \newtheorem{definition}{Definition} \def\bs{\bigskip}\def\ms{\medskip}\def\ds{\displaystyle} \renewcommand{\text}[1]{\quad\mbox{#1}\quad} \def\beq{\begin{equation}}\def\eeq{\end{equation}} \def\beqn{\begin{eqnarray}}\def\eeqn{\end{eqnarray}} \def\pont{\hspace{-6pt}{\bf.\ }} \def\eps{\varepsilon}\def\ffi{\varphi} \def\qed{\ifhmode\unskip\nobreak\fi\quad\ifmmode\Box\else$\Box$\fi} \title{ On the multi-colored Ramsey numbers\\ of paths and even cycles} \author{G\'{a}bor N. S\'ark\"ozy \thanks{Research supported in part by OTKA Grant No. K104343.}\\[-0.8ex] \small Alfr\'ed R\'enyi Institute of Mathematics\\[-0.8ex] \small Hungarian Academy of Sciences\\[-0.8ex] \small Budapest, P.O. Box 127\\[-0.8ex] \small Budapest, Hungary, H-1364\\ and\\ \small Computer Science Department\\[-0.8ex] \small Worcester Polytechnic Institute\\[-0.8ex] \small Worcester, MA, USA 01609\\[-0.8ex] \small \texttt{gsarkozy@cs.wpi.edu}} \date{\dateline{Oct 28, 2015}{Sep 20, 2016}{Sep 30, 2016}\\ \small Mathematics Subject Classifications: 05C55, 05C38.} \begin{document} \maketitle \begin{abstract} In this paper we improve the upper bound on the multi-color Ramsey numbers of paths and even cycles. More precisely, we prove the following. For every $r\geq 2$ there exists an $n_0=n_0(r)$ such that for $n\geq n_0$ we have $$R_r(P_n) \leq \left( r - \frac{r}{16r^3+1} \right) n.$$ For every $r\geq 2$ and even $n$ we have $$R_r(C_n) \leq \left( r - \frac{r}{16r^3+1} \right) n + o(n) \text{as} n\rightarrow \infty.$$ The main tool is a stability version of the Erd\H{o}s-Gallai theorem that may be of independent interest. \end{abstract} \section{Introduction: Ramsey numbers for paths and even cycles} For graphs $G_1, G_2, \ldots, G_r$, the Ramsey number $R(G_1, G_2, \ldots, G_r)$ is the smallest positive integer $n$ such that if the edges of a complete graph $K_n$ are partitioned into $r$ disjoint color classes giving $r$ graphs $H_1, H_2, \ldots, H_r$, then at least one $H_i$, $1\leq i \leq r$, has a subgraph isomorphic to $G_i$. The existence of such a positive integer is guaranteed by Ramsey's classical result \cite{RA}. The number $R(G_1, G_2, \ldots, G_r)$ is called the Ramsey number for the graphs $G_1, G_2, \ldots, G_r$. If every $G_i$ is the same graph $G$, then we use the notation $R_r(G)$. There is very little known about $R_r(G)$ for $r\geq 3$ even for very special graphs (see e.g. \cite{GRS} or \cite{RAD}). In this paper we consider the case when $G$ is either a path $P_n$ on $n$ vertices or a cycle $C_n$ for $n$ even. For $r=2$ a well-known theorem of Gerencs\'er and Gy\'arf\'as \cite{GG} states that $$R_2(P_n) = \left\lfloor \frac{3n-2}{2} \right\rfloor.$$ For $r=3$ Faudree and Schelp \cite{FS} conjectured the following $$R_3(P_n) = \left\{ \begin{array}{l} 2n - 1 \; \; \mbox{for odd} \; n,\\ 2n - 2 \; \; \mbox{for even} \; n. \end{array}\right.$$ In \cite{GRSS} we proved this conjecture for sufficiently large $n$ (but the conjecture is still open for every $n$). For $r\geq 4$ very little is known about $R_r(P_n)$. We can get a trivial upper bound by applying the Erd\H{o}s-Gallai extremal theorem (see Lemma \ref{eg} below) to the spanning subgraph induced by the edges of the most frequent color: \beq\label{trivi} R_r(P_n) \leq r n.\eeq As far as we know there is no better bound known in general even though we believe the truth is close to $(r-1)n$. The main result of this paper is to improve on (\ref{trivi}). \begin{theorem}\label{ut}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$ such that for $n\geq n_0$ we have $$R_r(P_n) \leq \left( r - \frac{r}{16r^3+1} \right) n.$$ \end{theorem} We make no attempt at optimizing the coefficient since it is probably far from optimal. The goal of this paper is to separate it from the trivial upper bound. Since in the proof we will only use the two most frequent colors, there seems to be room for improvement. We have a similar result for even cycles. It is believed that the Ramsey numbers for paths and even cycles are asymptotically the same via standard methods using the Regularity Lemma \cite{Sz} and the notion of connected matchings (see Lemma \ref{reg} below). This method was introduced by {\L}uczak \cite{L} and has been successfully used in many papers in this area (see for example \cite{BS}, \cite{FL}, \cite{GRSS}, \cite{KSS} and \cite{LSS}). Using this method and the Erd\H{o}s-Gallai extremal theorem, one can get an upper bound for the Ramsey number of even cycles (see \cite{LSS}): if $n$ is even we have \beq\label{trivi2}R_r(C_n) \leq r n + o(n) \text{as} n\rightarrow \infty.\eeq Here $r$ is fixed and $n$ is large. In the other direction, for an even $n$ the following lower bound is proved in \cite{YYFB} $$R_r(C_n) \geq (r-1) (n-2) + 2.$$ Here again we believe that the lower bound is close to the truth. In this paper we improve on (\ref{trivi2}). \begin{theorem}\label{kor}\pont For every $r\geq 2$ and even $n$ we have $$R_r(C_n) \leq \left( r - \frac{r}{16r^3+1} \right) n + o(n) \text{as} n\rightarrow \infty.$$ \end{theorem} \noindent After presenting the necessary tools in the next section, we give the proofs in Section \ref{proofs}. \section{Definitions and tools} We let $V(G)$ and $E(G)$ denote the vertex-set and the edge-set of the graph $G$. For a graph $G$ and a subset $U$ of its vertices, $G[U]$ is the restriction of $G$ to $U$. $N_G(v)$ is the set of neighbours of $v\in V(G)$. Hence $|N_G(v)|=deg_G(v)$, the degree of $v$. In $N_G(v)$ and $deg_G(v)$ we may omit the subscript $G$ if it is clear from the context. The average degree of a graph $G$ on $n$ vertices is the average of the degrees in $G$, i.e. $\sum_{v\in V(G)}deg(v)/n$. The first tool we will need is the classical result of Erd\H{o}s and Gallai \cite{EG} which determines the maximum number of edges in any graph on $n$ vertices if it contains no $P_k$. \begin{lemma}[\cite{EG}]\label{eg}\pont If $G$ is a graph on $n$ vertices containing no $P_k$, $k\geq 2$, then $$|E(G)|\leq \frac{k-2}{2} n,$$ with equality if and only if $k-1$ divides $n$ and all connected components of $G$ are complete graphs on $k-1$ vertices. \end{lemma} We will also need a similar result for connected graphs proved by Kopylov \cite{K} (see also \cite{BGLS} and \cite{FSI} for further details). \begin{lemma}[\cite{K}]\label{conn-EG}\pont Let $G$ be a connected graph on $n$ vertices containing no $P_k$, $n>k\geq 3$. Then $|E(G)|$ is bounded above by the maximum of ${k-2\choose 2} +(n-k+2)$ and ${\lceil k/2\rceil \choose 2} + \lfloor (k-2)/2\rfloor \left(n-\lceil \frac{k}{2} \rceil \right)$. \end{lemma} Finally the last lemma provides the fairly standard transition from paths to even cycles via connected matchings. \begin{lemma}[see Lemma 8 in \cite{LSS}]\label{reg}\pont Let a real number $c>0$ be given. If for every $\eps >0$ there exist a $\delta >0$ and an $n_0$ such that for every even $n>n_0$ and any graph $G$ with $|V(G)|>(1+\eps )cn$ and $|E(G)| \geq ( 1-\delta ) {|V(G)|\choose 2}$, any $r$-edge-coloring of $G$ has a monochromatic component containing a matching of $n/2$ edges, then $$R_r(C_n)\leq (c+o(1))n.$$ \end{lemma} \section{Proofs}\label{proofs} \subsection{Proof of Theorem \ref{ut}} We may assume throughout that $r\geq 4$, since we have precise results for $r=2$ and $r=3$. We may also assume that $n$ is sufficiently large compared to $r$. Theorem \ref{ut} follows easily from the following. \begin{lemma}\label{ket_szin}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$ such that for any $r$-colored complete graph on $n\geq n_0$ vertices one of the two most frequent colors contains a monochromatic path of length at least $\left(\frac{1}{r} + \frac{1}{16 r^4}\right) n$. \end{lemma} Indeed, if we consider an $r$-colored complete graph on at least $\left( r - \frac{r}{16r^3+1} \right) n$ vertices (where $n$ is sufficiently large) by Lemma \ref{ket_szin} one of the two most frequent colors contains a monochromatic path of length at least $$\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \left( r - \frac{r}{16r^3+1} \right) n = n,$$ proving Theorem \ref{ut}. To simplify the notation we put \beq\label{kx} k_r = \left\lceil \left(\frac{1}{r} + \frac{1}{16 r^4}\right) n\right\rceil \text{and} x_r = \left\lceil k_r \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \right\rceil.\eeq Lemma \ref{ket_szin} in turn will follow from the following lemma which can be viewed as a stability version of the Erd\H{o}s-Gallai theorem (Lemma \ref{eg}). Namely, either we have a slightly longer path than guaranteed by Lemma \ref{eg} or we are close to the extremal case: there are at most $r$ ``almost-cliques" that cover ``most" of the graph. \begin{lemma}\label{struktura}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$ such that if $G$ is a graph on $n\geq n_0$ vertices and $|E(G)| \geq \left(\frac{1}{r} - \frac{1}{8 r^5}\right) \frac{n^2}{2}$, then one of the following two cases must hold: \begin{itemize} \item[(a)] $G$ contains a path of length at least $k_r$, \item[(b)] There are at most $r$ connected components $C$ in $G$ such that for each $C$ we have $|C|\leq k_r+x_r$, together they cover at least $\left(1-\frac{1}{r}\right) n$ vertices and within each $C$ the average degree is at least $k_r-x_r$. \end{itemize} \end{lemma} {\bf Proof of Lemma \ref{struktura}:} We may assume that (a) does not hold, i.e. $G$ does not contain a path of length at least $k_r$, and we have to show that in this case (b) must be true. Let us take the connected components of $G$. First we show that we cannot have large components. \begin{claim}\label{nagy}\pont For every connected component $C$ of $G$, we have $|C| \leq k_r + x_r$. \end{claim} Assume to the contrary that we have a component $C$ with $|C| > k_r + x_r$. Put $n_1=|C|$ and $n_2=|V(G)\setminus C|$. Since $G$ does not contain a path of length $k_r$, we can apply Lemma \ref{eg} in $G[V(G)\setminus C]$ and Lemma \ref{conn-EG} in $G[C]$ with $k=k_r$. Indeed, applying Lemma \ref{conn-EG} in $G[C]$, the number of edges of $G$ within $C$ is at most \begin{align*} \max \left( \frac{k_r^2}{2} + n_1, \frac{k_r^2}{8} + \frac{k_r}{2} \left (n_1- \frac{k_r}{2} \right) \right) &= \max \left( \frac{k_r n_1}{2} - \frac{k_r(n_1-k_r)}{2} + n_1, \frac{k_r n_1}{2} - \frac{k_r^2}{8}\right) \\ &< \frac{k_r n_1}{2} - \min \left( \frac{k_r x_r}{2}, \frac{k_r^2}{8}\right) + n_1 = \frac{k_r n_1}{2} - \frac{k_r x_r}{2} + n_1. \end{align*} Here in the last line first we used that $n_1-k_r>x_r$, then $x_r < \frac{k_r}{4}$ (using (\ref{kx})). Then by applying Lemma \ref{eg} in $G[V(G)\setminus C]$, the number of edges of $G$ in $G[V(G)\setminus C]$ is at most $\frac{k_rn_2}{2}$. Thus altogether the number of edges in $G$ is at most \begin{align*} & \frac{k_r n_1}{2} - \frac{k_r x_r}{2} + n_1 + \frac{k_rn_2}{2} \leq \frac{k_rn}{2} - \frac{k_r x_r}{2} + n \\ \leq &\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \frac{n^2}{2} + \frac{n}{2} - \left(\frac{1}{r} + \frac{1}{16 r^4}\right)^2 \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \frac{n^2}{2} + n \\ \leq& \frac{1}{r}\frac{n^2}{2} + \frac{1}{16r^4}\frac{n^2}{2} - \frac{1}{16r^4}\frac{n^2}{2} - \frac{1}{8r^5}\frac{n^2}{2} - \frac{1}{16^2r^8} \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \frac{n^2}{2} + \frac{3n}{2} \\ < &\left(\frac{1}{r} - \frac{1}{8 r^5}\right) \frac{n^2}{2}\leq |E(G)|, \end{align*} if $n$ is sufficiently large (using (\ref{kx})), a contradiction. This finishes the proof of Claim \ref{nagy}. Let us denote by $\cal{C}$ the set of those components $C$ where the average degree is at least $k_r-x_r$. We will show that this is a good collection of components for (b) in Lemma \ref{struktura}. First we show that indeed the components in $\cal{C}$ together cover at least $\left( 1 - \frac{1}{r}\right)n$ vertices. \begin{claim}\label{unio}\pont We have $$\sum_{C\in \cal{C}} |C| \geq \left( 1 - \frac{1}{r}\right)n.$$ \end{claim} Indeed, we will use a similar argument as above for Claim \ref{nagy}. Put $n_1=\sum_{C\in \cal{C}} |C|$ and $n_2=|V(G)|-n_1$. Assume indirectly that $n_2 > \frac{n}{r}$. By applying Lemma \ref{eg} to $G[\bigcup _{C\in \cal{C}} C]$ and using the upper bound on the average degree in the remaining part, the number of edges in $G$ is less than \begin{align*} & \frac{k_r n_1}{2} + \frac{(k_r-x_r) n_2}{2} = \frac{k_r n}{2} - \frac{x_r n_2}{2} \\ \leq &\left(\frac{1}{r} + \frac{1}{16 r^4}\right) \frac{n^2}{2} + \frac{n}{2} - \left(\frac{1}{r} + \frac{1}{16 r^4}\right) \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \frac{n^2}{2r} \\ \leq &\frac{1}{r}\frac{n^2}{2} + \frac{1}{16r^4}\frac{n^2}{2} - \frac{1}{16r^4}\frac{n^2}{2} - \frac{1}{8r^5}\frac{n^2}{2} - \frac{1}{16 r^5} \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \frac{n^2}{2} + \frac{n}{2} \\ < &\left(\frac{1}{r} - \frac{1}{8 r^5}\right) \frac{n^2}{2}\leq |E(G)|, \end{align*} if $n$ is sufficiently large (using (\ref{kx}) and $n_2 > \frac{n}{r}$ in the second line), a contradiction. This finishes the proof of Claim \ref{unio}. Finally we show that indeed there are at most $r$ components in $\cal{C}$. \begin{claim}\label{r}\pont The number of connected components in $\cal{C}$ is at most $r$. \end{claim} Indeed, we show that we cannot have more than $r$ components in $\cal{C}$. Assume to the contrary that we have at least $r+1$ components in $\cal{C}$. Since the size of each $C$ in $\cal{C}$ is at least the average degree in $C$, the number of vertices in $G$ is at least \begin{align*} &(r+1) (k_r-x_r) \geq (r+1) \left(\frac{1}{r} + \frac{1}{16 r^4}\right) \left( 1 - \frac{1}{16r^2} - \frac{1}{8 r^3}\right) n - 2(r+1)\\ \geq &\left( 1 + \frac{1}{r} - \frac{1}{8r^2} - \frac{1}{4r^3} \right) n - 2(r+1) > n, \end{align*} if $n$ is sufficiently large (using $r\geq 4$), a contradiction. Thus indeed the components in $\cal{C}$ satisfy the conditions in (b), finishing the proof of Lemma \ref{struktura}. \qed Next we show how Lemma \ref{ket_szin} can be derived from Lemma \ref{struktura}, finishing the proof. {\bf Proof of Lemma \ref{ket_szin}:} Consider an $r$-colored graph $G$ on $n\geq n_0(r)$ vertices, where $n_0(r)$ is chosen sufficiently large so that Lemma \ref{struktura} and all subsequent inequalities hold. Let us take a most frequent color, say red, in $G$. The number of these red edges is at least \begin{align}\label{piros} \frac{1}{r} {n\choose 2} \geq \left( \frac{1}{r} - \frac{1}{8 r^5} \right) \frac{n^2}{2}, \end{align} so we may apply Lemma \ref{struktura} for the red subgraph. If (a) holds then we are done, therefore we may assume that (b) holds, i.e. there are $r$ red components with the properties given in (b) in Lemma \ref{struktura}. Furthermore, we may assume that the number of red edges is at most $\frac{k_rn}{2}$, since otherwise by Lemma \ref{eg} we would have (a), i.e. a red path of length at least $k_r$. Let us take a second most frequent color, say blue. The number of blue edges is at least \begin{align*} &\frac{1}{r-1} \left( {n\choose 2} - \frac{k_rn}{2} \right) \geq \frac{1}{r-1} \left( \frac{n^2}{2} - \left(\frac{1}{r} + \frac{1}{16 r^4}\right) \frac{n^2}{2} \right) - \frac{n}{r-1} \\ %\beq&\label{kek} &= \left(\frac{1}{r} - \frac{1}{16(r-1) r^4}\right) \frac{n^2}{2} - \frac{n}{r-1} \geq \left( \frac{1}{r} - \frac{1}{8 r^5} \right) \frac{n^2}{2}, \stepcounter{equation}\tag{\theequation}\label{kek}%\eeq \end{align*} so again we may apply Lemma \ref{struktura} for the blue subgraph as well. If (a) holds then we are done, therefore we may assume that (b) holds, i.e. there are $r$ blue components with the properties given in (b) in Lemma \ref{struktura}. We will show that this leads to a contradiction, i.e. in either the red subgraph or in the blue subgraph we must have (a). Consider the at most $r^2$ non-empty ``atoms" determined by the at most $r$ red components and the at most $r$ blue components, i.e. they are all the possible intersections of one of the at most $r$ red components with one of the at most $r$ blue components. Thus there exists an atom $A$ such that $A$ is a subset of a red component, it is also a subset of a blue component and \beq\label{|A|} |A| \geq \frac{1}{r^2} \left( 1 - \frac{2}{r} \right) n \geq \frac{n}{2r^2}\eeq (using $r\geq 4$). We will show that both the red and the blue subgraph contains more than half of the edges within $A$, a contradiction. Indeed, the number of missing edges in the red subgraph (and similarly for blue) within $A$ is at most $x_r(k_r+x_r)$. In order to see this, note that the number of missing edges in the red component $C$ containing the atom $A$ is at most $$\frac{|C| (|C|-(k_r-x_r))}{2} \leq \frac{(k_r+x_r)(k_r+x_r-(k_r-x_r))}{2} = x_r(k_r+x_r)$$ (using $|C|\leq k_r+x_r$ and that the average degree in $C$ is at least $k_r-x_r$), and then we assume the worst case, namely that all the missing edges in $C$ are missing within $A$. Then \begin{align*} x_r (k_r+x_r) \leq& \left(\frac{1}{r} + \frac{1}{16 r^4}\right)^2 \left(\frac{1}{16r^2} + \frac{1}{8 r^3}\right) \left(1 + \frac{1}{16r^2} + \frac{1}{8 r^3}\right) n^2 + n\\ \leq &\left(\frac{1}{16 r^4} + \frac{1}{8 r^5} + 16 \frac{1}{64 r^6} \right) n^2 + n \leq \left(\frac{1}{16 r^4} + \frac{1}{8 r^5} + \frac{1}{16 r^5} \right) n^2 + n\\ =&\left(\frac{1}{16 r^4} + \frac{3}{16 r^5} \right)n^2 + n < \frac{n^2}{8 r^4} - n \leq \frac{|A|^2}{4} - \frac{|A|}{4} = \frac{1}{2} {|A|\choose 2}, \end{align*} if $n$ is sufficiently large, as claimed. Here we used (\ref{|A|}), $r\geq 4$ and in the second line for each of the terms other than the two largest we used the upper bound $\frac{1}{64 r^6}$. This finishes the proof of Lemma \ref{ket_szin} and thus Theorem \ref{ut}. \qed \subsection{Proof of Theorem \ref{kor}} In light of Lemma \ref{reg} all we need is a ``perturbed" version of Lemma \ref{ket_szin} where we replace the complete graph with an almost-complete graph (Lemma \ref{struktura} needs no change). \begin{lemma}\label{ket_szin_eps}\pont For every $r\geq 2$ there exists an $n_0=n_0(r)$ and a $\delta=\delta(r)$ such that for any $r$-colored graph $G$ on $n\geq n_0$ vertices with $|E(G)| \geq (1-\delta ) {n\choose 2}$, one of the two most frequent colors contains a monochromatic path of length at least $\left(\frac{1}{r} + \frac{1}{16 r^4}\right) n$. \end{lemma} The proof of Lemma \ref{ket_szin_eps} is almost identical to the proof of Lemma \ref{ket_szin}, in both inequalities (\ref{piros}) and (\ref{kek}) we have room to spare: $$\frac{1}{r} (1-\delta ) {n\choose 2} \geq \left( \frac{1}{r} - \frac{1}{8 r^5} \right) \frac{n^2}{2},$$ and $$\frac{1}{r-1} \left( (1-\delta ){n\choose 2} - \frac{k_rn}{2} \right) \geq \frac{1}{r-1} \left( \frac{n^2}{2} - \left(\frac{1}{r} + \frac{1}{16 r^4}\right) \frac{n^2}{2} \right) - \frac{n}{r-1} - \frac{\delta}{r-1} {n\choose 2} $$ $$= \left(\frac{1}{r} - \frac{1}{16(r-1) r^4}\right) \frac{n^2}{2} - \frac{n}{r-1} - \frac{\delta}{r-1} {n\choose 2} \geq \left( \frac{1}{r} - \frac{1}{8 r^5} \right) \frac{n^2}{2},$$ if $\delta$ is sufficiently small compared to $\frac{1}{r}$. The rest of the proof is identical. To prove Theorem \ref{kor} we apply Lemma \ref{reg} and Lemma \ref{ket_szin_eps}. Indeed, for an arbitrary $0<\eps <1$ consider an $r$-colored graph on $N \geq (1 + \eps )\left( r - \frac{r}{16r^3+1} \right) n$ vertices with $|E(G)| \geq (1-\delta(r) ) {N\choose 2}$ (where $n$ is a sufficiently large even integer and $\delta(r)$ is from Lemma \ref{ket_szin_eps}). By Lemma \ref{ket_szin_eps} one of the two most frequent colors contains a monochromatic path of length at least $$\left(\frac{1}{r} + \frac{1}{16 r^4}\right) (1 + \eps ) \left( r - \frac{r}{16r^3+1} \right) n > n.$$ This implies the existence of a matching covering $n$ vertices in a monochromatic component. Hence, Lemma \ref{reg} implies that $R_r(C_n)\leq \left( r - \frac{r}{16r^3+1}+o(1)\right)n$. \qed \begin{thebibliography}{99} \bibitem{BGLS} P.N. Balister, E. Gy\H{o}ri, J. Lehel, R.H. Schelp, Connected graphs without long paths, {\em Discrete Mathematics} 308 (2008), pp. 4487-4494. \bibitem{BS} F.S. Benevides, J. Skokan, The 3-colored Ramsey number of even cycles, {\em Journal of Combinatorial Theory, Ser. B,} 99(4) (2009), pp. 690-708. \bibitem{EG} P. Erd\H{o}s, T. Gallai, On maximal paths and circuits of graphs, {\em Acta Math. Sci. Hungar.} 10 (1959), pp. 337-356. \bibitem{FS} R.J. Faudree, R.H. Schelp, Path Ramsey numbers in multicolorings, {\em Journal of Combinatorial Theory, Ser. B} 19 (1975), pp. 150-160. \bibitem{FL} A. Figaj, T. {\L}uczak, The Ramsey number for a triple of long even cycles, {\em Journal of Combinatorial Theory, Ser. B} 97 (2007), pp. 584-596. \bibitem{FSI} Z. F\"{u}redi, M. Simonovits, The history of degenerate (bipartite) extremal graph problems, {\em Bolyai Math. Studies} 25 pp. 169-264, Erd\H{o}s Centennial (L. Lov\'asz, I. Ruzsa, and V. T. S\'os, Eds.) Springer, 2013. Also see: \arxiv{1306.5167}. \bibitem{GG} L. Gerencs\'er, A. Gy\'arf\'as, On Ramsey-type problems, {\em Ann. Univ. Sci. Budapest E\"{o}tv\"{o}s Sect. Math.} 10 (1967), pp. 167-170. \bibitem{GRS} R.L. Graham, B.L. Rothschild, J.H. Spencer, {\em Ramsey Theory}, John Wiley \& Sons, 1990. \bibitem{GRSS} A. Gy\'arf\'as, M. Ruszink\'o, G.N. S\'ark\"ozy and E. Szemer\'edi, Three-color Ramsey number for paths, {\em Combinatorica}, 27(1) (2007), pp. 35-69. \bibitem{KSS} Y. Kohayakawa, M. Simonovits. J. Skokan, The $3$-colored Ramsey number of odd cycles, {\em Journal of Combinatorial Theory, Ser. B}, to appear. \bibitem{K} G.N. Kopylov, Maximal paths and cycles in a graph, {\em Dokl. Akad. Nauk SSSR} 234 (1977), pp. 19-21. (English translation: {\em Soviet Math. Dokl.} 18(3) (1977), pp. 593-596.) \bibitem{L} T. {\L}uczak, $R(C_n, C_n, C_n) \leq (4+o(1))n$, {\em Journal of Combinatorial Theory, Ser. B} 75 (1999), pp. 174-187. \bibitem{LSS} T. {\L}uczak, M. Simonovits, J. Skokan, On the multi-colored Ramsey numbers of cycles, {\em Journal of Graph Theory} 69 (2012), pp. 169-175. \bibitem{RAD} S.P. Radziszowski, Small Ramsey numbers, {\em Electronic Journal of Combinatorics}, (2002) DS1. \bibitem{RA} F.P. Ramsey, On a problem of formal logic, {\em Proc. London Math. Soc., 2nd Ser.}, 30 (1930), pp. 264-286. \bibitem{Sz} E. Szemer\'edi, Regular partitions of graphs, Colloques Internationaux C.N.R.S. $\mbox{N}^{\underline{o}}$ 260 - {\em Probl\`emes Combinatoires et Th\'eorie des Graphes}, Orsay (1976), 399-401. \bibitem{YYFB} Y. Sun, Y. Yang, F. Xu, B. Li, New lower bounds on the multicolor Ramsey numbers $R_r(C_{2m})$, {\em Graphs and Combinatorics} 22(2) (2006), pp. 283-288. \end{thebibliography} \end{document}