We show by an elementary argument that, given any greedy clique decomposition of a graph \(G\) with \(n\) vertices, the sum of the orders of the cliques is less than \(\frac{5}{8}n^2\). This gives support to a conjecture of Peter Winkler.
Citation
Gregory F. Bachelis, Troy Barcume, Xiang-Ying Su. On The Decomposition of Graphs Into Cliques[J], Ars Combinatoria, Volume 056. 129-131. .
