Cochromatic Number and the Genus of a Graph

The cochromatic number of a graph G , denoted by z ( G ), is the minimum number of subsets into which the vertex set of G can be partitioned so that each sbuset induces an empty or a complete subgraph of G . In this paper we introduce the problem of determining for a surface S , z ( S ), which is the maximum cochromatic number among all graphs G that embed in S . Some general bounds are obtained; for example, it is shown that if S is orientable of genus at least one, or if S is nonorientable of genus at least four, then z ( S ) is nonorientable of genus at least four, then z ( S )≤χ( S ). Here χ( S ) denotes the chromatic number S . Exact results are obtained for the sphere, the Klein bottle, and for S . It is conjectured that z ( S ) is equal to the maximum n for which the graph G n = K 1 ∪ K 2 ∪ … ∪ K n embeds in S .