On the difference between clique partition and clique covering numbers

Abstract

For a graph \(G\), let \(\operatorname{cp}(G)\) and \(\operatorname{cc}(G)\) be the minimum numbers of cliques in an edge partition and a clique cover of \(G\), respectively. Set ${\sigma }_n={\max }_{|V(G)|=n}(\mathrm{cp}(G)-\mathrm{cc}(G)),d_n=\lfloor \frac{n^2}{4}\rfloor -{\sigma }_n.$ In 1983, Erdős, Faudree, and Ordman asked whether \(d_n=O(n)\). Caccetta, Erdős, Ordman, and Pullman previously constructed graphs showing \(d_n=O(n^{3/2})\). We prove that $d_n=\Theta (n^{4/3}),$ thereby determining the correct order of the deficit and answering their question in the negative.

10 pages