Problem #1017: Let $f(n,k)$ be such that every graph on $n$ vertices and...

---

Progress

The function $f(n,k)$ is sometimes called the clique partition number.

Erdős, Goodman, and Pósa [EGP66] proved that $f(n,k)\leq n^2/4$ for all $k$ (and in fact the complete graphs can be taken to be edges and triangles), which is best possible in general, as witnessed for example by a complete bipartite graph. In [Er71] Erdő asks vaguely whether this result can be 'sharpened' for $k>n^2/4$.

Lovász [Lo68] proved that every graph on $n$ vertices and $k$ edges is the union of $\binom{n}{2}-k+t$ complete graphs, where $t$ is maximal such that $t^2-t\leq \binom{n}{2}-k$, but without the assumption that the complete graphs are edge disjoint. Lovász's result is sharp in many cases.

If $k>n^2/4$ and the graph contains no $K_4$ then this is equivalent to finding the minimum number of edge disjoint triangles. This special case was also asked about by Erdős. A complete answer was provided by Györi and Keszegh [GyKe17], who proved that every $K_4$-free graph with $n$ vertices and $\lfloor n^2/4\rfloor+m$ edges contins $m$ pairwise edge disjoint triangles.

See also [184] for an analogous problem decomposing into edges and cycles, and [583] for decomposing into paths. The clique partition problem for chordal graphs is the subject of [81].