Local Rainbow Colorings for Various Graphs

Motivated by a problem in theoretical computer science suggested by Wigderson, Alon and Ben-Eliezer studied the following extremal problem systematically one decade ago. Given a graph H, let $C(n,H)$ be the minimum number k such that the following holds. There are n colorings of E(Kₙ) with k colors, each associated with one of the vertices of Kₙ, such that for every copy T of H in Kₙ, at least one of the colorings that are associated with $V(T)$ assigns distinct colors to all the edges of $E(T)$. In this paper, we obtain several new results in this problem including: For paths of short length, we show that C(n,P₄)=Ω(n1/5) and C(n,Pₜ)=Ω(n1/3) with t∈\5,6\, which significantly improve the previously known lower bounds (logn)Ω(1). We make progress on the problem of Alon and Ben-Eliezer about complete graphs, more precisely, we show that C(n,Kᵣ)=Ω(n2/3) when r 8, and C(n,Ks,t)=Ω(n2/3) for all t s 7. When H is a star with at least $4$ leaves, a matching of size at least $4$, or a path of length at least $7$, we give a new lower bound for $C(n,H)$. We also show that for any graph H with at least $6$ edges, $C(n,H)$ is polynomial in n. All of these improve the corresponding results obtained by Alon and Ben-Eliezer.