1979/03/01 by H. Joseph Straight · 2 citations
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Graph Labeling and Dimension Problems #Combinatorics #Mathematics #Klein bottle #Genus #Graph #Vertex (graph theory) #Chromatic scale #Discrete mathematics #Torus #Botany
paper · doi:10.1002/jgt.3190030106
openalex publication_date 1979/03/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/05/21
Abstract 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 .