We investigate the existence of such colorings in surfaces, and the complexity of defective coloring problems. It is shown that a toroidal graph is $(3,2)$- and $(5,1)$- colorable, and that a graph of genus $\gamma$ is $(\chi_\gamma /(d+1) + 4,d)$-colorable, where $\chi_\gamma$ is the maximum chromatic number of a graph embeddable on the surface of genus $\gamma$. It is shown that the $(2,k)$-coloring, for $k \geq 1$, and the $(3,1)$-coloring problems are NP-complete even for planar graphs. In general graphs $(k,d)$-coloring is NP-complete for $k \geq 3$, $d \geq 0$. The tightness is considered. Also, generalizations to defects of several algorithms for approximate (proper) coloring are presented.
The second relaxation of vertex coloring we considered is when adjacent vertices can be given the same color, with only the restriction that connected monochromatic subgraphs must be regions of diameter at most $d$. Surprisingly, as Linial and Saks showed in 1991, any graph with $n$ vertices has a $\log_2 n$-color network decomposition with $d = 2 \log n$, and a simple construction will find it in near-linear time. If there is time, we will discuss some recent results on existence and complexity for this problem as well.
We conclude with some open problems.