On the difference between clique partition and clique covering numbers of graphs

Abstract

For a graph $G$, let $\cpn(G)$ and $\ccn(G)$ denote the minimum numbers of cliques whose edge sets partition and cover $E(G)$, respectively, and put $f(n)=\max_{|V(G)|=n}\bigl(\cpn(G)-\ccn(G)\bigr).$ In 1983, Erdős, Faudree, and Ordman asked whether there is a sequence of graphs $G_n$ such that $|V(G_n)|=n$ and $\cpn(G_n)-\ccn(G_n)=n^2/4+O(n)$. The question appears as Problem 66 in Chung's survey \cite{ChungProblems} and is also listed on the UCSD Erdős Problems website. Caccetta, Erdős, Ordman, and Pullman proved that $f(n)=n^2/4-o(n^2)$. We prove that $f(n)=\lfloor \frac{n^2}{4}\rfloor -\Theta (n^{4/3}),$ and hence answer the question in the negative.

10 pages