##
**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 **limsup**_{n ––> 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-(2^{r}-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