For any graph, there is a largest integer k such that given any partit
ion of the vertex set with at most k elements in each class of the par
tition, there is transversal of the partition that is a dominating set
in the graph. Some basic results about this parameter, the partition
domination number, are obtained. In particular, it is shown that its v
alue is 2 for the two-dimensional infinite grid, and that determining
whether a given vertex partition admits a dominating transversal is NP
-complete, even for a graph which is a simple path. The existence of v
arious dominating transversals in certain partitions in regular graphs
is studied as well. (C) 1996 John Wiley & Sons, Inc.