# Difference of clique partition number to clique covering number

The clique partition number, $$cp(G)$$, is the least number of cliques that partition the edge set of $$G$$. The clique cover number, $$cc(G)$$, is the minimum number of cliques which cover all edges of a graph $$G$$.

In 1983, Erdös, Faudree and Ordman proposed the following problem.

# Problem [1]

Is there a sequence of graphs $$G_n$$ such that $cp(G_n)-cc(G_n) = n^2/4 + O(n)?$

In 1985, Caccetta, Erdös, Ordman and Pullman [2] found a sequence $$G_n$$ such that

$$\displaystyle cp(G_n)-cc(G_n) = n^2/4 -n^{3/2}/2+ n/4+O(1).$$

Bibliography
1 P. Erdös, R. Faudree and E. Ordman, Clique partitions and clique coverings, Proceedings of the First Japan Conference on Graph Theory and Applications (Hakone, 1986), Discrete Math. 72 (1988), 93-101.

2 L. Caccetta, P. Erdös, E. T. Ordman and N. J. Pullman, The difference between the clique numbers of a graph, Ars Combinatoria 19 (1985) A, 97-106.