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 {Gn} is a family of graphs such that z(Gn) = n, then there is a positive c such that the size of Gn is at least cn2 log2n; also d(n) = \theta(n2 ln2n) 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