Nordhaus and Gaddum proved sharp upper and lower bounds on the sum and product of the chromatic number of a graph and its complement. Over the years, similar inequalities have been shown for a plenitude of different graph invariants. In this paper, we consider such inequalities for the number of cliques (complete subgraphs) in a graph $G$, denoted $k(G)$. We note that some such inequalities have been well-studied, e.g., lower bounds on $k(G)+k(\overline{G})=k(G)+i(G)$, where $i(G)$ is the number of independent subsets of $G$, has been come to be known as the study of Ramsey multiplicity. We give a history of such problems. One could consider fixed sized versions of these problems as well. We also investigate multicolor versions of these problems, meaning we $r$-color the edges of $K_n$ yielding graphs $G_1,G_2,\ldots,G_r$ and give bounds on $\sum k(G_i)$ and $\prod k(G_i)$.
@article{10_37236_13158,
author = {Deepak Bal and Jonathan Cutler and Luke Pebody},
title = {On the number of monochromatic cliques in a graph},
journal = {The electronic journal of combinatorics},
year = {2025},
volume = {32},
number = {3},
doi = {10.37236/13158},
zbl = {8097644},
url = {http://geodesic.mathdoc.fr/articles/10.37236/13158/}
}
TY - JOUR
AU - Deepak Bal
AU - Jonathan Cutler
AU - Luke Pebody
TI - On the number of monochromatic cliques in a graph
JO - The electronic journal of combinatorics
PY - 2025
VL - 32
IS - 3
UR - http://geodesic.mathdoc.fr/articles/10.37236/13158/
DO - 10.37236/13158
ID - 10_37236_13158
ER -
%0 Journal Article
%A Deepak Bal
%A Jonathan Cutler
%A Luke Pebody
%T On the number of monochromatic cliques in a graph
%J The electronic journal of combinatorics
%D 2025
%V 32
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/13158/
%R 10.37236/13158
%F 10_37236_13158
Deepak Bal; Jonathan Cutler; Luke Pebody. On the number of monochromatic cliques in a graph. The electronic journal of combinatorics, Tome 32 (2025) no. 3. doi: 10.37236/13158
