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 Kn (i.e. a partition of Kn into r monochromatic edgedisjoint subgraphs), what is the largest subset B of vertices of Kn 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