AbstractThe cochromatic number of a graphG, denoted byz(G), is the minimum number of subsets into which the vertex set ofGcan be partitioned so that each sbuset induces an empty or a complete subgraph ofG. In this paper we introduce the problem of determining for a surfaceS,z(S), which is the maximum cochromatic number among all graphsGthat embed inS. Some general bounds are obtained; for example, it is shown that ifSis orientable of genus at least one, or ifSis nonorientable of genus at least four, thenz(S) is nonorientable of genus at least four, thenz(S)≤χ(S). Here χ(S) denotes the chromatic numberS. Exact results are obtained for the sphere, the Klein bottle, and forS. It is conjectured thatz(S) is equal to the maximumnfor which the graphGn=K1∪K2∪ … ∪K