On the difference between clique partition and clique covering numbers

摘要: 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_{\lvert V(G)\rvert=n}= \bigl(\operatorname{cp}(G)-\operatorname{cc}(G)\bigr), d_n=\left\lfloor\frac{n^2}{4}\right\rfloor-\sigma_n.$ In 1983, Erd\H{o}s, Faudree, and Ordman asked whether \(d_n=O(n)\). Caccetta, Erd\H{o}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.