##
**Zentralblatt MATH**

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

**Zbl.No: ** 708.05057

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

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

**Source: ** J. Graph Theory 13, No.6, 713-718 (1989).

**Review: ** A 2-colored graph G is a graph with edges colored red or blue. A set X\subset V(G) r-dominates (b-dominates) Y\subset V(G) if X\cap Y = Øand for each y in Y there exists x in X such that the edge (x,y) is red (blue). The set X\subset V(G) dominates Y\subset V(G) if either X r-dominates Y or X b-dominates Y. A set A on t vertices is said to dominate all but at most k vertices of G if A dominates B and |V(G)-A-B| \leq k. The following conjecture is due to the first author and *A. Hajnal* [Ramsey type theorems, Preprint (1987), Discrete Appl. Math. 25, No. ½, 37-52 (1989; Zbl 715.05052)]. For given positive integers n, t, any 2-colored complete graph K_{n} of order n has a set X_{t} of at most t vertices dominating all but at most n/2^{t} vertices of K_{n}. The authors prove this conjecture by proving the following more general result. Let G = [X,Y] be a 2- colored complete bipartite graph, t be a nonnegative integer, and \beta in (0,1). Then at least one of the following two statements is true:

1. Some subset of at most t vertices of X r-dominates all but at most \beta^{t+1}(|X|+|Y|) vertices of Y.

2. Some subset of at most t vertices of Y b-dominates all but at most (1-\beta)^{t+1}(|X|+|Y|) vertices of X.

The proof of this result is constructive, in fact, it is a greedy-type low-order polynomial algorithm which finds the required (red or blue) dominating set.

**Reviewer: ** D.Lick

**Classif.: ** * 05C99 Graph theory

68R10 Graph theory in connection with computer science

**Keywords: ** r-domination; dominating set

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag