Problem 1017

Erdős Problem #1017: declared status 'open'. Formalized: no. Let $f(n,k)$ be such that every graph on $n$ vertices and $k$ edges can be partitioned into at most $f(n,k)$ edge-disjoint complete graphs. Estimate $f(n,k)$ for $k>n^2/4$. Current best: Lov\'{a}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. Prize: no. Tags: graph theory.