DEFECTIVE COLORING REVISITED

A graph is (k, d)-colorable if one can color the vertices with k color s such that no vertex is adjacent to more than d vertices of its same color. In this paper we investigate the existence of such colorings in surfaces and the complexity of coloring problems. It is shown that a toroidal graph is (3, 2)- and (5, 1)-colorable, and that a graph of ge nus gamma is (chi(gamma)/(d + 1) + 4, d)-colorable, where chi(gamma) i s the maximum chromatic number of a graph embeddable on the surface of genus gamma. It is shown that the (2, k)-coloring, for k greater than or equal to 1, and the (3, 1)-coloring problems are NP-complete even for planar graphs. In general graphs (k, d)-coloring is NP-complete fo r k greater than or equal to 3, d greater than or equal to 0. The tigh tness is considered. Also, generalizations to defects of several algor ithms for approximate (proper) coloring are presented. (C) 1997 John W iley & Sons, Inc.