Premium
Cochromatic Number and the Genus of a Graph
Author(s) -
Straight H. Joseph
Publication year - 1979
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190030106
Subject(s) - combinatorics , mathematics , klein bottle , genus , graph , vertex (graph theory) , chromatic scale , discrete mathematics , torus , botany , geometry , biology
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 .