Finding a monochromatic subgraph or a rainbow path |
| |
| Authors: | András Gyárfás Jenő Lehel Richard H Schelp |
| |
| Institution: | 1. Computer and Automation Research Institute of the Hungarian Academy of Sciences, Budapest, P. O. Box 63, 1518 Hungary;2. Department of Mathematical Sciences, the University of Memphis, Memphis, Tennessee 38152;3. On leave from the Computer and Automation Research Institute of the Hungarian Academy of Sciences. |
| |
| Abstract: | For simple graphs G and H, let f(G,H) denote the least integer N such that every coloring of the edges of KN contains either a monochromatic copy of G or a rainbow copy of H. Here we investigate f(G,H) when H = Pk. We show that even if the number of colors is unrestricted when defining f(G,H), the function f(G,Pk), for k = 4 and 5, equals the (k ? 2)‐ coloring diagonal Ramsey number of G. © 2006 Wiley Periodicals, Inc. J Graph Theory |
| |
| Keywords: | Ramsey theory anti‐Ramsey problems multicolored path local 2‐coloring |
|
|
