##
**Zentralblatt MATH**

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

**Zbl.No: ** 679.05040

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Ordman, Edward T.

**Title: ** Clique partitions and clique coverings. (In English)

**Source: ** Discrete Math. 72, No.1-3, 93-101 (1988).

**Review: ** Only undirected graphs without loops or multiple edges are considered here. K_{n} is a clique on n vertices. The clique covering number and the clique partition number of the graph G is denoted by cc(G) and cp(G)respectively. The authors obtain asymptotic results for cp(K_{n}-K_{m}) for m in the range \sqrt{n} < m < n; for example if m = cn^{a}, ½ < a < 1, then cp(K_{n}-K_{m}) is asymptotic to c^{2}n^{2a}. They apply bounds developed in this connection to bound the maximum value of cp(G)/cc(G) on graphs G with n vertices, showing it can grow as fast as cn^{2} where c > 1/64. Further they prove that if T_{n} is K_{n} minus a matching then, for all n, (log n)-1 \leq cc(T_{n}) \leq 2(log n).

**Reviewer: ** B.Andrásfai

**Classif.: ** * 05C35 Extremal problems (graph theory)

05C70 Factorization, etc.

**Keywords: ** clique covering number; clique partition number; asymptotic results; bounds

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag