##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 704.05039

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Gould, R.J.; Gyárfás, A.; Rousseau, C.; Schelp, R.H.

**Title: ** Monochromatic coverings in colored complete graphs. (In English)

**Source: ** Combinatorics, graph theory, and computing, Proc. 20th Southeast Conf., Boca Raton/FL (USA) 1989, Congr. Numerantium 71, 29-38 (1990).

**Review: ** [For the entire collection see Zbl 688.00003.]

For given positive integers, t, r and n, and an r-colouring of the edges of K_{n} (i.e. a partition of K_{n} into r monochromatic edgedisjoint subgraphs), what is the largest subset B of vertices of K_{n} necessarily monochromatically covered by some t-element subset of the vertices? (The set A monochromatically covers B if there is a colour c such that for all b in B-Athere is an a in A with (a,b) of colour c.) In the case r = 2 it was proved by *P. Erdös*, *J. Faudree*, *A. Gyárfás* and *R. H. Schelp* [J. Graph Theory 13, 713-718 (1989)] that there are at most t vertices which monochromatically cover at least (1- ½^{t})n vertices. The present paper gives partial answers for r \geq 3. It is proved that for r = 3 there exist at most 22 vertices which monochromatically cover at most 22 vertices which monochromatically cover at least 2n/3 of the vertices. Some evidence is given that perhaps the number 22 can be replaced by 3, which by an example of Kierstead would be the best possible for r = t = 3. The example shows that a natural generalization of the (r = 2)-case does not hold. However, for t fixed, r fixed and large, and n large with respect to r, the generalization essentially holds.

**Reviewer: ** B.Toft

**Classif.: ** * 05C70 Factorization, etc.

**Keywords: ** partition; domination; covering

**Citations: ** Zbl 688.00003

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag