Rainbow triangles and cliques in edge-colored graphs

For an edge-colored graph, a subgraph is called rainbow if all its edges have distinct colors. We show that if G is an edge colored graph of order n and size m using c colors on its edges, and m + c >= (n+1 2) + k - 1 for a non-negative integer k, then G contains at least k rainbow triangles. For n >= 3k, we show that this result is best possible, and we completely characterize the class of edge-colored graphs for which this result is sharp. Furthermore, we show that an edge-colored graph G contains at least k rainbow triangles if Sigma(v is an element of V(G)) d(G)(c)(v) >= (n+1 2) + k - 1 where d(G)(c)(v) denotes the number of distinct colors incident to a vertex v. Finally we characterize the edge-colored graphs without a rainbow clique of size at least six that maximizes the sum of edges and colors m + c. Our results answer two questions of Fujita et al., 2019. (C) 2019 Elsevier Ltd. All rights reserved.