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.
展开▼
