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

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