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 $σ_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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.20305
curl -X POST /api/v1/records/arxiv/2609.20305/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.20305/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'