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