PreprintarXiv licencearXiv
On the difference between clique partition and clique covering numbers
Abstract
For a graph G, let cp(G) and cc(G) be the minimum numbers of cliques in an edge partition and a clique cover of G, respectively. Set σn = maxlvert V(G)rvert=n (cp(G)−cc(G)), dn=⌊n2/4⌋−σn. In 1983, Erdős, Faudree, and Ordman asked whether dn=O(n). Caccetta, Erdős, Ordman, and Pullman previously constructed graphs showing dn=O(n3/2). We prove that dn=Θ(n4/3), thereby determining the correct order of the deficit and answering their question in the negative.
Related
- Clique and chromatic numbers of graph powers: spectral bounds and anticodes
- Cayley Tournaments Simultaneously Critical for the Clique and Dichromatic Numbers
- P-adic Curved Kakeya Sets, Projection Theorem and Covering Numbers
- Links of minimum degree and exact covering numbers
- Boundedness and Separation Between Induced and Non-Induced Covering Numbers
BibTeX
@misc{ning2026difference,
title = {{On the difference between clique partition and clique covering numbers}},
author = {Bo Ning},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.20305},
eprint = {2609.20305},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.20305},
}
RIS
TY - UNPB
TI - On the difference between clique partition and clique covering numbers
AU - Bo Ning
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.20305
UR - https://arxiv.org/abs/2609.20305
AB - For a graph G, let cp(G) and 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 (cp(G)−cc(G)), d_n=⌊n^2/4⌋−σ_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 negative.
ER -