##
**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 c_{1} and c_{2} for which for n > m_{0}(c_{1},c_{2}) c_{1}\frac{n}{(log n)^{3}} < **max** \frac{f(G(n))}{h(G(n))} < c_{2}\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