Local rainbow colorings (Q433480): Difference between revisions

From the authors' abstract: ``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(K_n)\) with \(k\) colors, each associated with one of the vertices of \(K_n\), such that for every copy \(T\) of \(H\) in \(K_n\) 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.''