## 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 Kn and G\ne Kn-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