##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 721.05020

**Autor: ** Erdös, Paul; Gimbel, John; Straight, H.Joseph

**Title: ** Chromatic number versus chromatic number in graphs with bounded clique number. (In English)

**Source: ** Eur. J. Comb. 11, No.3, 235-240 (1990).

**Review: ** The cochromatic number z(G) of a graph G is the minimum number of sets into which the vertices of G can be partitioned so that each set is independent in G or induces a complete subgraph of G. The present paper proves the existence ofa function f(n) with the following property: If G does not contain a complete n-graph K_{n} and G\ne K_{n-1}, then the usual chromatic number \chi(G) is at most z(G)+f(n). Moreover it is proved that f(n) is exponential in n and that f(3) = 1 and f(4) = 1.

**Reviewer: ** B.Toft (Odense)

**Classif.: ** * 05C15 Chromatic theory of graphs and maps

05C35 Extremal problems (graph theory)

**Keywords: ** clique number; cochromatic number

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag