Zentralblatt MATH

Publications of (and about) Paul Erdös
Zbl.No:  573.05034
Autor:  Caccetta, Louis; Erdös, Paul; Ordman, Edward T.; Pullman, Norman J.
Title:  The difference between the clique numbers of a graph. (In English)
Source:  Ars Comb. 19A, 97-106 (1985).
Review:  The least number of complete subgraphs of a graph G with n vertices needed to partition (cover) the edge set of G is denoted by cp(G) (cc(G), respectively). Main result: n2/4-n3/2/2+n/4 \leq cp(G)-cc(G) \leq n2/4-2.
Reviewer:  J.Plesnik
Classif.:  * 05C35 Extremal problems (graph theory)
                   05C70 Factorization, etc.
Keywords:  clique covering; clique partition; edge covering; complete subgraphs

© 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