Ratio 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\). Let \( G_n\) denote a graph on \( n\) vertices.

Problem (proposed by Erdös, Faudree and Ordman)

Determine the largest value \( c\) such that

\(\displaystyle \frac {cp (G_n)}{cc(G_n)} > c n^2 \)

for infinitely many values of \( n\).

An example was given in [1] with \( c = 1/64\).

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.