## Zentralblatt MATH

Publications of (and about) Paul Erdös

Zbl.No:  791.05038
Autor:  Erdös, Paul; Gimbel, John
Title:  Some problems and results in cochromatic theory. (In English)
Source:  Gimbel, John (ed.) et al., Quo vadis, graph theory? A source book for challenges and directions. Amsterdam: North-Holland, Ann. Discrete Math. 55, 261-264 (1993).
Review:  Given a graph G, the cochromatic number z(G) of G is the fewest number of parts into which V(G) must be partitioned so that each part induces in G either an empty or complete graph. The authors survey some of the most interesting open questions involving cochromatic numbers. For example, let z(n) denote the maximum cochromatic number among all graphs with order n. Then it can be shown that z(n) = \Theta({n \over ln n}). However, even for some small values of n (e.g. n = 12), the exact value of z(n) is unknown. This paper includes open questions relating the cochromatic number and size, genus, chromatic number and clique number.