Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2406.03355 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929375546441728 |
|---|---|
| author | Bal, Deepak Cutler, Jonathan Pebody, Luke |
| author_facet | Bal, Deepak Cutler, Jonathan Pebody, Luke |
| contents | 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)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2406_03355 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Nordhaus-Gaddum inequalities for the number of cliques in a graph Bal, Deepak Cutler, Jonathan Pebody, Luke Combinatorics 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)$. |
| title | Nordhaus-Gaddum inequalities for the number of cliques in a graph |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2406.03355 |