Tripartite Ramsey numbers for paths |
| |
| Authors: | András Gyárfás Miklós Ruszinkó Gábor N. Sárközy Endre Szemerédi |
| |
| Affiliation: | 1. Computer and Automation Research Institute, Hungarian Academy of Sciences, Budapest, P.O. Box 63, Budapest, Hungary, H‐1518;2. Computer Science Department, Worcester Polytechnic Institute, Worcester, Massachusetts, 01609;3. Computer Science Department, Rutgers University, New Brunswick, New Jersey, 08903 |
| |
| Abstract: | In this article, we study the tripartite Ramsey numbers of paths. We show that in any two‐coloring of the edges of the complete tripartite graph K(n, n, n) there is a monochromatic path of length (1 ? o(1))2n. Since R(P2n+1,P2n+1)=3n, this means that the length of the longest monochromatic path is about the same when two‐colorings of K3n and K(n, n, n) are considered. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 164–174, 2007 |
| |
| Keywords: | regularity lemma paths Ramsey numbers |
|
|
