  A graph $G$ is $(d_1,\ldots,d_k)$-colorable if its vertex set can be
partitioned into $k$ sets $V_1,\ldots,V_k$, such that for each $i\in\{1,
\ldots, k\}$, the subgraph of $G$ induced by $V_i$ has maximum degree at most
$d_i$. The Four Color Theorem states that every planar graph is
$(0,0,0,0)$-colorable, and a classical result of Cowen, Cowen, and Woodall
shows that every planar graph is $(2,2,2)$-colorable. In this paper, we extend
both of these results to graphs on surfaces. Namely, we show that every graph
embeddable on a surface of Euler genus $g>0$ is $(0,0,0,9g-4)$-colorable and
$(2,2,9g-4)$-colorable. Moreover, these graphs are also
$(0,0,O(\sqrt{g}),O(\sqrt{g}))$-colorable and
$(2,O(\sqrt{g}),O(\sqrt{g}))$-colorable. We also prove that every triangle-free
graph that is embeddable on a surface of Euler genus $g$ is $(0, 0,
O(g))$-colorable. This is an extension of Gr\"{o}tzsch's Theorem, which states
that triangle-free planar graphs are $(0, 0, 0)$-colorable. Finally, we prove
that every graph of girth at least 7 that is embeddable on a surface of Euler
genus $g$ is $(0,O(\sqrt{g}))$-colorable. All these results are best possible
in several ways as the girth condition is sharp, the constant maximum degrees
cannot be improved, and the bounds on the maximum degrees depending on $g$ are
tight up to a constant multiplicative factor.
