Metraipolis › archive › dc_0791cfe53888

On the difference between clique partition and clique covering numbers — arXiv:2609.20305

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.20305
License (as archived)
CC0-1.0
Archived
2026-10-10T04:47:18.246Z
SHA-256 of the archived text
d06b7b9f0e81b6675b7d9f78f3bce7ec6803ff2a19e0613572f97218965bbfc2
Stable URL of this page
https://metraipolis.com/documento/dc_0791cfe53888

How to cite

On the difference between clique partition and clique covering numbers — arXiv:2609.20305 — arXiv (en), https://arxiv.org/abs/2609.20305 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_0791cfe53888 (Metraipolis archive dc_0791cfe53888, sha256 d06b7b9f0e81b6675b7d9f78f3bce7ec6803ff2a19e0613572f97218965bbfc2)
BibTeX
@misc{dc0791cfe53888,
  title = {On the difference between clique partition and clique covering numbers — arXiv:2609.20305},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.20305},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_0791cfe53888; sha256 d06b7b9f0e81b6675b7d9f78f3bce7ec6803ff2a19e0613572f97218965bbfc2},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.20305. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\sigma_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-\sigma_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=\Theta(n^{4/3}),$ thereby determining the correct order of the deficit and answering their question in the negative.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-18 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2609.20305 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-10T04:15:33.146Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-18?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).