{"id":"arxiv/2608.11536","url":"https://arxiv.org/abs/2608.11536","tags":["math.CO"],"score":0,"title":"On the difference between clique partition and clique covering numbers of graphs","domain":"math.CO","source":"arxiv","authors":["Bo Ning"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-12","reactions":{}}