Given a graph H, we denote by C(n,H) the minimum number k such that the following holds. There are n colorings of E(Kn) with k-colors, each associated with one of the vertices of Kn, such that for every copy T of H in Kn, at least one of the colorings that are associated with V (T ) assigns distinct colors to all the edges of E(T ). We characterize the set of all graphs H for which C(n,H) is bounded by some absolute constant c(H), prove a general upper bound and obtain lower and upper bounds for several graphs of special interest. A special case of our results partially answers an extremal question of Karchmer and Wigderson motivated by the investigation of the computational power of span programs.