VERTEX TRANSVERSALS THAT DOMINATE

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.