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.