๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Note on the cochromatic number of several surfaces

โœ Scribed by H. Joseph Straight

Publisher
John Wiley and Sons
Year
1980
Tongue
English
Weight
151 KB
Volume
4
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

โœฆ Synopsis

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 subset induces an empty or a complete subgraph of G. In an earlier work, the author considered the problem of determining z(S), the maximum cochromatic number among all graphs that embed in a surface S. The value of z(S) was found for the sphere, the Klein bottle, and for the nonorientable surface of genus 4. In this note, some recent results of Albertson and Hutchinson are used to determine the cochromatic numbers of the projective plane and the nonorientable surface of genus 3. These results lend further evidence to support the conjecture that z(S) is equal to the maximum n for which the graph G~n~ = K~1~ U K~2~ U โ€ฆ U K~n~ embeds in S.

๐Ÿ“œ SIMILAR VOLUMES

Cochromatic Number and the Genus of a Gr
Cochromatic Number and the Genus of a Graph
โœ H. Joseph Straight ๐Ÿ“‚ Article ๐Ÿ“… 1979 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 310 KB ๐Ÿ‘ 1 views

## 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 surf

Note on irreducible triangulations of su
Note on irreducible triangulations of surfaces
โœ Atsuhiro Nakamoto; Katsuhiro Ota ๐Ÿ“‚ Article ๐Ÿ“… 1995 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 302 KB ๐Ÿ‘ 1 views

## Abstract In this paper, we shall show that an irreducible triangulation of a closed surface __F__^2^ has at most __cg__ vertices, where __g__ stands for a genus of __F__^2^ and __c__ a constant. ยฉ 1995, John Wiley & Sons, Inc.

The number of defective colorings of gra
The number of defective colorings of graphs on surfaces
โœ Tom Rackham ๐Ÿ“‚ Article ๐Ÿ“… 2010 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 99 KB ๐Ÿ‘ 1 views

A (k, 1)-coloring of a graph is a vertex-coloring with k colors such that each vertex is permitted at most 1 neighbor of the same color. We show that every planar graph has at least c n distinct (4, 1)-colorings, where c is constant and โ‰ˆ 1.466 satisfies 3 = 2 +1. On the other hand for any >0, we gi

A note on the star chromatic number
A note on the star chromatic number
โœ J. A. Bondy; Pavol Hell ๐Ÿ“‚ Article ๐Ÿ“… 1990 ๐Ÿ› John Wiley and Sons ๐ŸŒ English โš– 176 KB ๐Ÿ‘ 1 views

## Abstract A. Vince introduced a natural generalization of graph coloring and proved some basic facts, revealing it to be a concept of interest. His work relies on continuous methods. In this note we make some simple observations that lead to a purely combinatorial treatment. Our methods yield sho