  We give a linear-time algorithm to decide 3-colorability (and find a
3-coloring, if it exists) of quadrangulations of a fixed surface. The algorithm
also allows to prescribe the coloring for a bounded number of vertices.
