Zentralblatt MATH
Publications of (and about) Paul Erdös
Zbl.No: 485.05052
Autor: Erdös, Paul
Title: On the covering of the vertices of a graph by cliques. (In English)
Source: J. Math. Res. Expo. 1982, No.1, 93-96 (1982).
Review: Let G(n) be a graph of n vertices. Denote by f(G(n)) = t the smallest integer for which the vertices of G(n) can be covered by t cliques. Denote furthr by h(G(n)) = \ell the largest integer for which there are \ell edges of G(n), no two are in the same clique. K. R. Parthasarathy and S.A.Choudum [J. Math. Phys. Sci. Madras 10, 255-261 (1976; Zbl 335.05125)] conjectured that if G(n) has no isolated vertices then (1) f(G(n)) \leq h(G(n)) holds for all graphs. A simple application of the probability method shows that (1) fails for almost graphs, as shown in the following theorem: There are positive absolute constants c1 and c2 for which for n > m0(c1,c2) c1\frac{n}{(log n)3} < max \frac{f(G(n))}{h(G(n))} < c2\frac{n}{(log n)3}.
Reviewer: J.-H.Tian
Classif.: * 05C70 Factorization, etc.
05C30 Enumeration of graphs and maps
05C35 Extremal problems (graph theory)
Keywords: clique covering
Citations: Zbl.335.05126
© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag