De Caen–Erdős–Pullman–Wormald clique-partition conjecture

Let $\mathcal{G}_n$ be the set of all graphs on $n$ vertices, let $\overline{G}$ denote the complement of a graph $G$, and let $\operatorname{cp}(G)$ be the minimum number of cliques whose edge sets partition the edges of $G$. Define

$$M_n=\max_{G\in\mathcal{G}_n}\left(\operatorname{cp}(G)+\operatorname{cp}(\overline{G})\right).$$

De Caen–Erdős–Pullman–Wormald conjecture.

$$M_n\sim\frac{7}{25}n^2.$$

The known bounds are $\frac{7n^2}{25}+O(n)\leq M_n\leq\frac{13n^2}{30}+O(n)$. Thus the conjecture asserts that the lower bound is asymptotically tight, while closing this gap remains open.