Let $G = (V,E)$ be an $n$-vertex graph and let $c: E \to \mathbb{ N}$ be a coloring of its edges. Let $d^c(v)$ be the number of distinct colors on the edges at $v \in V$ and let $\delta^c(G) = \min_{ v \in V} \{ d^{ c}(v) \}$. H. Li proved that $\delta^c(G) > n/2$ guarantees a rainbow triangle in $G$. We give extensions of Li's result to cliques $K_r$ for $r \ge 4$.

Categories: math.CO

Rainbow Cliques in Edge-Colored Graphs