Id: arxiv/2609.20305 Url: https://arxiv.org/abs/2609.20305 Tags: math.CO Score: 0 Title: On the difference between clique partition and clique covering numbers Domain: math.CO Source: arxiv Authors: Bo Ning Reviews: 0 Subject: math.CO Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-01 Page: https://delphi.science/r/arxiv/2609.20305 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 $σ_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-σ_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=Θ(n^{4/3}),$ thereby determining the correct order of the deficit and answering their question in the…