Journal of Combinatorics
Volume 2 (2011)
Local rainbow colorings
Pages: 293 – 304
Given a graph $H$, we denote by $C(n,H)$ the minimum number $k$ suchthat the following holds. There are $n$ colorings of $E(K_n)$ with$k$-colors, each associated with one of the vertices of $K_n$, suchthat for every copy $T$ of $H$ in $K_n$, at least one of the coloringsthat are associated with $V(T)$ assigns distinct colors to all theedges of $E(T)$.
We characterize the set of all graphs $H$ for which $C(n,H)$ is boundedby some absolute constant $c(H)$, prove a general upper bound andobtain lower and upper bounds for several graphs of special interest. Aspecial case of our results partially answers an extremal question ofKarchmer and Wigderson motivated by the investigation of thecomputational power of span programs.