##
**Zentralblatt MATH**

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

**Zbl.No: ** 743.05047

**Autor: ** Erdös, Paul; Gimbel, John; Kratsch, Dieter

**Title: ** Some extremal results in cochromatic and dichromatic theory. (In English)

**Source: ** J. Graph Theory 15, No.6, 579-585 (1991).

**Review: ** For a graph G, the cochromatic number of G, denoted z(G), is the least m for which there is a partition of the vertex set of G having order m, where each part induces a complete or empty graph. Given a digraph D, the dichromatic number d(D) of D is the order of the smallest partition of V(D) where each part induces an acyclic digraph. For an undirected graph G, the dichromatic number of G, denoted d(G), is the maximum dichromatic number of all orientations of G. Let m be an integer; by d(m) is denoted the minimum size of all graphs G where d(G) = m. In this paper it is proved that if **{**G_{n}**}** is a family of graphs such that z(G_{n}) = n, then there is a positive c such that the size of G_{n} is at least cn^{2} log^{2}n; also d(n) = \theta(n^{2} ln^{2}n) holds. The proof uses R. M. Wilson's asymptotic results about the existence of pairwise balanced designs [J. Comb. Theory, Ser. A 18, 71-79 (1975; Zbl 295.05002)].

**Reviewer: ** I.Tomescu (Bucuresti)

**Classif.: ** * 05C80 Random graphs

05C15 Chromatic theory of graphs and maps

05C35 Extremal problems (graph theory)

05C20 Directed graphs (digraphs)

**Keywords: ** random graph; perfect graph; clique number; cochromatic number; dichromatic number

**Citations: ** Zbl 295.05002

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag