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