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.
Reviewer: L.Lesniak Foster (Madison)
Classif.: * 05C15 Chromatic theory of graphs and maps
00A07 Problem books
Keywords: cochromatic number; complete graph
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag