Consider a partition of the edge set of a graph \(G\) into cliques (pairwise adjacent vertices). What is the minimum number of cliques in such a partition? If \(G\) has \(n\) vertices, then this number is clearly at most \(n(n-1)/2\), since each edge of \(G\) is itself a clique. Erdős, Goodman, and Pósa showed in 1966 that this bound can indeed be decreased to \(\lfloor n^2/4 \rfloor\), which is optimal (as shown by balanced complete bipartite graphs). Furthermore, their clique partition only uses cliques of size 2 and 3. Győri and Kostochka, Kahn, and Chung independently proved the following strengthening: if every clique on \(i\) vertices has weight \(i\), then there is a partition of the edge set into cliques of total weight at most \(2 \lfloor n^2/4 \rfloor\).
Erdős conjectured the following further strengthening: if every clique on \(i\) vertices has weight \(i-1\), then there is a partition of the edge set into cliques of total weight at most \(\lfloor n^2/4 \rfloor\). The authors first prove a fractional relaxation of the conjecture and explain more generally how to solve such problems fractionnally for arbitrary weight functions. They then use their fractional result to show an asymptotic version of the original conjecture: if every clique on \(i\) vertices has weight \(i-1\), then there is a partition of the edge set into cliques of total weight at most \((1+o(1)) n^2/4\).
The authors also consider the clique cover problem, when instead of covering all edges the goal is to cover all cliques of size \(t\) for some fixed \(t\). Using their framework they show an asymptotic version of a conjecture of Dau, Milenkovic, and Puleo, stating that the minimum number of cliques in such a cover is maximized for balanced complete \(t\)-partite graphs.
The conjecture of Erdős mentioned above and the conjecture of Dau, Milenkovic, and Puleo were recently solved for all sufficiently large values of \(n\), see here. The proofs heavily rely on the ideas and ingredients introduced in the present paper.