Cochromatic Number and the Genus of a Graph
Author:
- 1 March 1979
- journal article
- Published by Wiley in Journal of Graph Theory
- Vol. 3 (1) , 43-51
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 Gn = K1 ∪ K2 ∪ … ∪ Kn embeds in S.Keywords
This publication has 6 references indexed in Scilit:
- Generalized Embedding SchemesJournal of Graph Theory, 1978
- Blocks and the nonorientable genus of graphsJournal of Graph Theory, 1977
- Every planar map is four colorableBulletin of the American Mathematical Society, 1976
- The maximum size of an independent set in a nonplanar graphBulletin of the American Mathematical Society, 1975
- SOLUTION OF THE HEAWOOD MAP-COLORING PROBLEMProceedings of the National Academy of Sciences, 1968
- Map-Colour TheoremsCanadian Journal of Mathematics, 1952