Publications of (and about) Paul Erdös
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.
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