{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-01","reactions":{}}