✦ LIBER ✦

Cochromatic Number and the Genus of a Graph

✍ Scribed by H. Joseph Straight

Publisher: John Wiley and Sons
Year: 1979
Tongue: English
Weight: 310 KB
Volume: 3
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190030106

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 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.

📜 SIMILAR VOLUMES

Subgraphs with a large cochromatic numbe

Subgraphs with a large cochromatic number

✍ Alon, Noga; Krivelevich, Michael; Sundakov, Benny 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 66 KB

The cochromatic number of a graph G = (V, E) is the smallest number of parts in a partition of V in which each part is either an independent set or induces a complete subgraph. We show that if the chromatic number of G is n, then G contains a subgraph with cochromatic number at least Ω( n ln n ). Th

The maximum interval number of graphs wi

The maximum interval number of graphs with given genus

✍ Edward R. Scheinerman 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 202 KB 👁 1 views

The interval number of a graph G, denoted i(G), is the least positive integer t such that G is the intersection graph of sets, each of which is the union of t compact real intervals. It is known that every planar graph has interval number at most 3 and that this result is best possible. We investiga

Note on the cochromatic number of severa

Note on the cochromatic number of several surfaces

✍ H. Joseph Straight 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 151 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 subset induces an empty or a complete subgraph of __G__. In an earlier work, the author considered the problem of determi

The Relative Maximum Genus of a Graph

✍ C.P. Bonnington 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 422 KB

Face Size and the Maximum Genus of a Gra

Face Size and the Maximum Genus of a Graph 1. Simple Graphs

✍ Yuanqiu Huang; Yanpei Liu 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 150 KB

This paper shows that a simple graph which can be cellularly embedded on some closed surface in such a way that the size of each face does not exceed 7 is upper embeddable. This settles one of two conjectures posed by Nedela and S8 koviera (1990, in ``Topics in Combinatorics and Graph Theory,'' pp.

Blocks and the nonorientable genus of gr

Blocks and the nonorientable genus of graphs

✍ Saul Stahl; Lowell W. Beineke 📂 Article 📅 1977 🏛 John Wiley and Sons 🌐 English ⚖ 183 KB 👁 1 views

## Abstract Examples are given to show that the nonorientable genus of a graph is not additive over its blocks. A nonorientable analog for the Battle, Harary, Kodama, and Youngs Theorem is proved; this completely determines the nonorientable genus of a graph in terms of its blocks. It is also shown