Rainbow Cliques in Edge-Colored Graphs

Abstract

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 $\hat{I}{´}^c(G)={\min }_{v\in V}\{d^c(v)\}$. H. Li proved that $\hat{I}{´}^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$.

16 pages