More on Rainbow Cliques in Edge-Colored Graphs

Abstract

In an edge-colored graph $G$, a rainbow clique $K_k$ is a $k$-complete subgraph in which all the edges have distinct colors. Let $e(G)$ and $c(G)$ be the number of edges and colors in $G$, respectively. In this paper, we show that for any $\epsilon >0$, if $e(G)+c(G)\ge (1+\frac{k-3}{k-2}+2\epsilon )\left(\genfrac{}{}{0ex}{}{n}{2}\right)$ and $k\ge 3$, then for sufficiently large $n$, the number of rainbow cliques $K_k$ in $G$ is $\hat{I}\text{c◯}(n^k)$. We also characterize the extremal graphs $G$ without a rainbow clique $K_k$, for $k=4,5$, when $e(G)+c(G)$ is maximum. Our results not only address existing questions but also complete the findings of Ehard and Mohr (Ehard and Mohr, Rainbow triangles and cliques in edge-colored graphs. {\it European Journal of Combinatorics, 84:103037,2020}).

16pages