# 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$$.

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.