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. Kn 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(Kn-Km) for m in the range \sqrt{n} < m < n; for example if m = cna, ½ < a < 1, then cp(Kn-Km) is asymptotic to c2n2a. 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 cn2 where c > 1/64. Further they prove that if Tn is Kn minus a matching then, for all n, (log n)-1 \leq cc(Tn) \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