PreprintCC BY 4.0arXiv
Range of Clique Counts in Graphs
Abstract
Let γ(G) denote the number of cliques in a graph G and let Γ(n):= {γ(G):|V(G)|=n} be the set of values of γ(G) that can be attained on n vertices. We improve on a result by Erdős and Erné to show that | Γ(n)| ≥ 2n−4ln(2)log3(n) for sufficiently large n.
Related
- Exact Clique Counts in Graphs with a Forbidden Tree
- Clique counts under degree and matching constraints
- Counterexamples to two conjectures on the diameter of clique-free graphs
- The 𝒜α-Spectral Turán Problem for s-Clique Tensors of Kr+1-Free Graphs
- Bounded chromatic number of graphs with small clique number and large minimum degree
BibTeX
@misc{neve2026range,
title = {{Range of Clique Counts in Graphs}},
author = {Mihir Neve and Alexey Pokrovskiy and Andrey Shapiro},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21739},
eprint = {2609.21739},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21739},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Range of Clique Counts in Graphs
AU - Mihir Neve
AU - Alexey Pokrovskiy
AU - Andrey Shapiro
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21739
UR - https://arxiv.org/abs/2609.21739
AB - Let γ(G) denote the number of cliques in a graph G and let Γ(n):= {γ(G):|V(G)|=n} be the set of values of γ(G) that can be attained on n vertices. We improve on a result by Erdős and Erné to show that | Γ(n)| ≥ 2^n−4ln(2)log^3(n) for sufficiently large n.
ER -