Maximum product of clique partition numbers for complementary graphs

The clique partition number, \( cp(G)\), is the least number of cliques that partition the edge set of \( G\).


What is \[ \max\{cp(G) cp(\bar{G})\} \] where \(G\) ranges over all graphs on \(n\) vertices?

The best bound known [1] is

\[ \frac{29}{2000} n^4 + O(n^3) \leq \max\{cp(G) cp(\bar{G})\} \leq \frac{169}{3600}n^4 + O(n^3) . \]

A sum variation of this problem was proposed by Erdős and solved by Pyber [2] where he proved

\(\displaystyle cc(G)+cc(\bar{G}) \le \frac{1}{4}n^2+2\)

However, it appears that no recent progress has been made on the original problem.

1 D. de Caen, P. Erdös, N. J. Pullmann and N. C. Wormald, Extremal clique coverings of complementary graphs, Combinatorica 6 (1986) no. 4, 309-314.

2 L. Pyber, Clique Covering of Graphs, Combinatorica 6 (1986) no. 4, 393-398