## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  787.05071
Autor:  Erdös, Paul; Galvin, Fred
Title:  Monochromatic infinite paths. (In English)
Source:  Discrete Math. 113, No.1-3, 59-70 (1993).
Review:  Let K\omega denote the complete graph on the natural numbers. It is shown that if the edges of K\omega are colored with 2 colors, then there is a monochromatic infinite path P with upper density \geq 2/3, where the upper density for P is limsupn ––> oo|V(P)\cap{1,2,...,n}|/n. It is also shown that there is a monochromatic infinite path P such that the set {1,2,...,n} contains at least the first .21n vertices of the path P. Corresponding results are obtained for coloring K\omega with r colors for r \geq 3, and upper bounds are given for various density conditions on infinite monochromatic paths. For example it is shown that the edges of K\omega can be colored with r colors such that every (r-1)-colored path has upper density \leq 1-(2r-1)-2.
Reviewer:  R.Faudree (Memphis)
Classif.:  * 05C55 Generalized Ramsey theory
05C38 Paths and cycles
05C15 Chromatic theory of graphs and maps
Keywords:  monochromatic infinite path; coloring; density

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag