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

Books Problems Set Theory Combinatorics Extremal Probl/Ramsey Th.
Graph Theory Add.Number Theory Mult.Number Theory Analysis Geometry
Probabability Personalia About Paul Erdös Publication Year Home Page