Estimate f(n,k), the clique partition number for graphs with more than n²/4 edges (Erdős #1017)
Statement
A clique partition of a graph $G$ is a set of edge-disjoint complete subgraphs whose edge sets partition $E(G)$. Let $f(n,k)$ be the maximum, over all graphs $G$ on $n$ vertices with exactly $k$ edges, of the minimum number of cliques in a clique partition of $G$ (equivalently: the least $f$ such that every $n$-vertex, $k$-edge graph can be partitioned into at most $f$ edge-disjoint complete graphs). Estimate $f(n,k)$ in the range $k>n^2/4$.
Acceptance. FULLY RESOLVES: determine the asymptotics (or exact value) of $f(n,k)$ for $k>n^2/4$ — a proven estimate strictly sharpening the Erdős–Goodman–Pósa bound $f(n,k)\leq n^2/4$ in this range (an upper bound of the form $n^2/4-\varphi(n,k)$ together with matching constructions), with a complete proof. ADVANCES, any of: (a) prove a nontrivial improvement over the $n^2/4$ bound for some explicit sub-range of $k>n^2/4$, with a matching extremal construction; (b) compute exact values $f(n,k)$ for new small $n$ by exhaustive/ILP search, delivering the extremal graph, a certificate that its clique partition number equals the claimed value, and a certificate that no $n$-vertex, $k$-edge graph exceeds it; (c) extend the Győri–Keszegh exact edge-disjoint-triangle result to a broader graph class. Deliver the proof, or the extremal graphs + optimal clique partitions + exhaustiveness certificate.
Background
Posed by Erdős [Er71]; $f(n,k)$ is the (worst-case) clique partition number. Erdős, Goodman and Pósa [EGP66] proved $f(n,k)\leq n^2/4$ for all $k$ — and in fact the cliques can always be taken to be single edges and triangles — which is best possible in general (a complete bipartite graph needs about $n^2/4$). Erdős asked whether this bound can be sharpened in the denser regime $k>n^2/4$. Lovász [Lo68] proved that every $n$-vertex, $k$-edge graph is a union (not necessarily edge-disjoint) of $\binom{n}{2}-k+t$ complete graphs, where $t$ is maximal with $t^2-t\leq \binom{n}{2}-k$, sharp in many cases. In the special case $k>n^2/4$ with $G$ being $K_4$-free, a clique partition reduces to a minimum set of edge-disjoint triangles, and Győri and Keszegh [GyKe17] gave the complete answer: every $K_4$-free graph on $n$ vertices with $\lfloor n^2/4\rfloor+m$ edges contains $m$ pairwise edge-disjoint triangles. Related decomposition problems: edges and cycles (erdosproblems.com/184), paths (erdosproblems.com/583), and the chordal case (erdosproblems.com/81). Listed as open on erdosproblems.com/1017 (fetched 2026-07-13, status 'open', tagged 'graph theory'). Attacker's tool: ILP / exhaustive computation of clique partition numbers for small $n$ to map $f(n,k)$ in the $k>n^2/4$ regime and expose the extremal graphs.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Erdős Problem #1017 (T. F. Bloom) | website |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.