Journal of Combinatorics

Volume 2 (2011)

Number 2

Local rainbow colorings

Pages: 293 – 304



Noga Alon (Blavatnik School of Computer Science, Tel Aviv University, Israel; Institute for Advanced Study, Princeton, N.J., U.S.A.)

Ido Ben-Eliezer (Blavatnik School of Computer Science, Tel Aviv University, Israel)


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.

Full Text (PDF format)