# Reference request: monochromatic paths in edge-colored complete graphs

Given $k,c \in \mathbb{N}$, let $P(k,c)$ be the minimum $n$ such that no matter how we color the edges of the complete graph $K_n$ with $c$ colors, there is always a monochromatic path of length $k$.

What are the best known upper and lower bounds for $P(k,c)$?

For $c=2$, it is a theorem of Gerencsér and Gyárfás that $P(k,2)=\lfloor (3k-2)/2 \rfloor$.

For $c=3$, Gyárfás, Ruszinkó, Sárközy and Szemerédi proved that for sufficiently large $k$, $P(k,3)=2k-1$ if $k$ is odd, and $2k-2$ if $k$ is even.

The exact asymptotics are unknown for larger values of $c$ (as far as I know).

• I think these results would be for paths with $k$ vertices; the question is about paths of length $k$, so $k+1$ vertices. – Jan Kyncl Apr 15 '15 at 17:08
• Yes, you are right that these results are for paths with $k$ vertices. For this question, I conveniently regarded a path of length $k$ as a path with $k$ vertices (the notion of the length of a path is somewhat ambiguous, although I usually consider the length as the number of edges). – Tony Huynh Apr 15 '15 at 17:11

For the multi-color Ramsey numbers of even cycles, Luczak, Simonovits and Skokan proved that $R(C_k;c)\le ck+o(k)$ for fixed number $c$ of colors and $k\rightarrow \infty$.

For odd cycles, Bondy and Erdos claim that $R(C_k;c)\le (c+2)!k$.

Both upper bounds apply also for paths with $k$ vertices since $P(k-1,c) \le R(C_k;c)$.