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

# Problem

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.