Clique partitions and clique coverings

AbstractSeveral new tools are presented for determining the number of cliques needed to (edge-)partition a graph. For a graph on n vertices, the clique partition number can grow cn2 times as fast as the clique covering number, where c is at least 164. If in clique on n vertices, the edges between cna vertices are deleted, 12⩽a<1, then the number of cliques needed to partition what is left is asymptotic to c2n2a; this fills in a gap between results of Wallis for a<12 and Pullman and Donald for a=1, c > 12. Clique coverings of a clique minus a matching are also investigated